Borgen i Tavira er en ruin med en have i. Kernen er maurisk, fra 1000- til 1200-tallet, bygget af stampet ler, men det meste af det synlige murværk er yngre: kong Dinis' ombygning omkring 1292 og 1900-tallets restaureringer. Det mangekantede tårn er borgens mest usædvanlige træk. Kristne styrker tog byen omkring 1242, jordskælvet i 1755 skadede borgen alvorligt, og i første halvdel af 1800-tallet var borggården byens kirkegård. Siden 1938 har den været have. Fra murene ser man hele byen, floden, lagunen og saltpanderne, og den udsigt er hele forklaringen på, at murene ligger her.
Tavira blev først en rigtig by under maurerne. Udgravningerne i bykernen har ikke fundet noget ældre end 1000-tallet; et enkelt fønikisk murstykke er fundet i byen, men derefter er der fjorten århundreders stilhed. De første mure rejste almoraviderne efter al sandsynlighed sidst i 1000-tallet eller i 1100-tallet, og almohaderne byggede om i taipa, stampet ler presset mellem forskallinger. Det mangekantede albarrã-tårn tilskrives dem; det er ombygget mange gange siden. Fra 1144 holdt Tavira sig uafhængig under skiftende lokale herrer, Ibn Munīb og siden Alī al-Wahībī, modstod en almohadisk belejring i 1157 og faldt først i 1167-68. Byen inden for murene dækkede godt fire hektar. Nede ved Praça da República fandt man en port med hesteskobue; resterne står i det islamiske museumsrum på pladsen. Formen er arabisk, ligesom byens navn.
Mellem 1239 og 1242 erobrede de kristne byen; krøniken tilskriver det Dom Paio Peres Correia, stormester for Santiagoordenen. Legenden siger, at det var hævn: syv af ordenens riddere var blevet dræbt af maurere under en jagt ved Antas, mens der var våbenhvile. Kong Sancho II gav Tavira til ordenen i 1244, og kronen fik byen tilbage i 1272. I 1266 fik Tavira som den første by i Algarve sit charter af Afonso III. Kong Dinis lod fæstningen genopbygge i 1292 med borgtårn og en ringmur med syv porte. Porta de D. Manuel er gotisk og ældre end sit navn; Manuel I's våben kom på omkring 1500, og i 1520 gjorde han Tavira til by og kaldte den Algarves vigtigste handelshavn.
Fra 1400-tallet mistede borgen sin militære betydning, selvom den fik bastionsværker efter 1640. Jordskælvet i 1755 skadede den alvorligt, og store dele af bymuren blev taget ned i de følgende århundreder. I første halvdel af 1800-tallet var borggården Taviras kirkegård, travlest under koleraepidemien i 1832. I 1938 købte kommunen grunden og anlagde Jardim do Castelo, og året efter blev borgen fredet. Tilbage står flere firkantede tårne, det mangekantede tårn og lange stræk af ringmuren. Åbent hver dag, om sommeren 8.30-19.
Sankt Hans nat ved midnat, siger man i Tavira, viser en maurisk pige sig i ruinerne. Hun var datter af borgens mauriske herre, Aben Fabila, som fortryllede hende, da Dom Paio stormede byen, og hun venter på den, der kan bryde trolddommen. I nogle genfortællinger stiger hun op af en brønd, i andre var det en kristen ridder, hun elskede.
Gå op på murene tidligt på dagen, før solen står højt, så har man det bedste lys over byen og floden. Paio Peres Correia og de syv riddere ligger begravet i Igreja de Santa Maria do Castelo, få meter fra borgporten; kirken står, hvor moskéen lå, og urtårnet menes at være minareten.
Højen ved Gilão var det sted, hvorfra man kunne dække vadestedet over floden, før der var nogen bro. Derfor byggede maurerne her, og derfor kæmpede kristne og maurere om stedet. Med artilleriet mistede borgen sin militære betydning fra 1400-tallet, men den forblev guvernørens sæde og et tegn på kongemagt, og murene blev repareret igen og igen, efter klager på cortes i 1475 og med nye værker efter 1640.
Borgen står som ruin, men den er mere restaureret, end den ser ud: staten genopbyggede indgangsbuen og hele murpartier i 1940, et murstræk i 1969 og konsoliderede tårnet 1982-89. Man har sikret og fyldt ud, ikke bygget en ny borg. Det gør den mindre imponerende på afstand, men mere ærlig tæt på: man kan se lagene af taipa, middelalderlig kvadersten og 1900-tallets reparationer i samme mur.