Le château de Tavira est une ruine avec un jardin dedans. Le noyau est maure, du XIe au XIIIe siècle, bâti en terre damée, mais l'essentiel de la maçonnerie visible est plus récent : la reconstruction du roi Dinis vers 1292 et les restaurations du XXe siècle. La tour polygonale est le trait le plus insolite du château. Les forces chrétiennes prirent la ville vers 1242, le tremblement de terre de 1755 endommagea gravement le château et, dans la première moitié du XIXe siècle, la cour du château fut le cimetière de la ville. Depuis 1938, c'est un jardin. Des remparts, on voit toute la ville, le fleuve, la lagune et les marais salants, et cette vue est toute l'explication de la présence des murs ici.
Tavira n'est devenue une vraie ville que sous les Maures. Les fouilles dans le centre ancien n'ont rien trouvé d'antérieur au XIe siècle ; un seul pan de mur phénicien a été découvert dans la ville, mais ensuite ce sont quatorze siècles de silence. Les premiers remparts furent selon toute vraisemblance élevés par les Almoravides à la fin du XIe siècle ou au XIIe, et les Almohades reconstruisirent en taipa, de la terre damée pressée entre des coffrages. La tour albarrã polygonale leur est attribuée ; elle a été remaniée bien des fois depuis. À partir de 1144, Tavira se maintint indépendante sous des seigneurs locaux successifs, Ibn Munīb puis Alī al-Wahībī, résista à un siège almohade en 1157 et ne tomba qu'en 1167-68. La ville intra-muros couvrait un peu plus de quatre hectares. En bas, près de la Praça da República, on a trouvé une porte à arc outrepassé ; les vestiges se voient dans la salle muséale islamique de la place. La forme est arabe, comme le nom de la ville.
Entre 1239 et 1242, les chrétiens conquirent la ville ; la chronique l'attribue à Dom Paio Peres Correia, grand maître de l'ordre de Santiago. La légende dit que ce fut une vengeance : sept chevaliers de l'ordre avaient été tués par des Maures pendant une chasse près d'Antas, alors qu'une trêve était en vigueur. Le roi Sancho II donna Tavira à l'ordre en 1244, et la couronne reprit la ville en 1272. En 1266, Tavira fut la première ville de l'Algarve à recevoir sa charte, d'Afonso III. Le roi Dinis fit reconstruire la forteresse en 1292, avec un donjon et une enceinte à sept portes. La Porta de D. Manuel est gothique et plus ancienne que son nom ; les armes de Manuel I y furent apposées vers 1500, et en 1520 il éleva Tavira au rang de cité et la qualifia de principal port de commerce de l'Algarve.
À partir du XVe siècle, le château perdit son importance militaire, même s'il reçut des ouvrages bastionnés après 1640. Le tremblement de terre de 1755 l'endommagea gravement, et de grandes parties de l'enceinte urbaine furent démolies au cours des siècles suivants. Dans la première moitié du XIXe siècle, la cour du château fut le cimetière de Tavira, le plus fréquenté pendant l'épidémie de choléra de 1832. En 1938, la municipalité acheta le terrain et aménagea le Jardim do Castelo, et l'année suivante le château fut classé. Il reste plusieurs tours carrées, la tour polygonale et de longs tronçons de l'enceinte. Ouvert tous les jours, en été de 8 h 30 à 19 h.
La nuit de la Saint-Jean, à minuit, dit-on à Tavira, une jeune Maure apparaît dans les ruines. Elle était la fille du seigneur maure du château, Aben Fabila, qui l'enchanta quand Dom Paio prit la ville d'assaut, et elle attend celui qui saura rompre le sortilège. Dans certaines versions, elle sort d'un puits ; dans d'autres, c'est un chevalier chrétien qu'elle aimait.
Montez sur les remparts tôt dans la journée, avant que le soleil soit haut, pour avoir la meilleure lumière sur la ville et le fleuve. Paio Peres Correia et les sept chevaliers reposent dans l'Igreja de Santa Maria do Castelo, à quelques mètres de la porte du château ; l'église se dresse là où se trouvait la mosquée, et la tour de l'horloge passe pour être le minaret.
La colline au bord du Gilão était l'endroit d'où l'on pouvait couvrir le gué sur le fleuve, avant qu'il y ait un pont. C'est pourquoi les Maures ont bâti ici, et pourquoi chrétiens et Maures se sont disputé le lieu. Avec l'artillerie, le château perdit son importance militaire à partir du XVe siècle, mais il resta le siège du gouverneur et un signe du pouvoir royal, et les murs furent réparés encore et encore, après des plaintes aux cortès de 1475 et avec de nouveaux ouvrages après 1640.
Le château se présente comme une ruine, mais il est plus restauré qu'il n'y paraît : l'État a reconstruit l'arc d'entrée et des pans entiers de murs en 1940, un tronçon de mur en 1969, et a consolidé la tour en 1982-89. On a sécurisé et comblé, pas bâti un château neuf. Cela le rend moins impressionnant de loin, mais plus honnête de près : on voit dans le même mur les couches de taipa, la pierre de taille médiévale et les réparations du XXe siècle.