Eén van de mooie kuststadjes van de Portugese Algarve is Tavira. De rijke geschiedenis ervan gaat terug tot de 8ste eeuw v.Chr. toen de Feniciërs hier een stad bouwden, compleet met een stadsmuur, tempels en een haven. Het ging om een Fenicische handelspost. De nederzetting situeerde zich boven op de heuvel waar nu de ruïnes van het Castelo de Tavira staan zoals blijkt uit een deel van de muur dat dateert uit de 8e eeuw v. Chr. en dat aan het licht kwam tijdens een archeologische campagne in 1997. Deze stad werd twee eeuwen later vernietigd door de Turdetani die de heuvel tijdens de 5de en de 4de eeuw bewoonden. Ze verbouwden het fort en veranderden de naam van de plaats in Talábriga. Deze nederzetting werd verlaten en vervangen door het oppidum van Cerro do Cavaco dat zich één kilometer ten noorden van Tavira situeert en van het einde van de 4de tot het einde van de 1ste eeuw v. Chr. werd bewoond. Cerro do Cavaco overleefde de regering van Augustus niet.
Toch werd Tavira in de Romeinse tijd opnieuw bewoond, maar de grenzen van het stedelijk gebied blijven tot op de dag van vandaag onduidelijk. Het centrum situeerde zich ongeveer vijf kilometer westwaarts van het huidige Tavira in de wijk Luz. De naam van deze stad was Balsa die zich tot zowat de grootste Romeinse havenstad van Hispania Lusitania ontwikkelde met thermen, een amfitheater, een paardenrenbaan, een theater en vele pakhuizen. Het stedelijke centrum had een buitengewone omvang voor een gemeente die geen hoofdstad was. Op het hoogtepunt besloeg Balsa een oppervlakte van 45 hectare. Dat is meer dan Olisipo (Lissabon) of Ossonoba (Faro), waardoor het zich tot de grote steden van Lusitania mocht rekenen. Het grondgebied van de civitas kwam min of meer overeen met het hedendaagse Oost-Algarve met zijn heuvels die rijk waren aan bossen en mineralen. Het grensde aan de provincie Baetica. De kust werd gevormd door lagunes en estuaria die in de Romeinse tijd door de agro-maritieme activiteiten op grote schaal werden geëxploiteerd. Aanzienlijke sporen van de Romeinse centuriatio zijn nog steeds terug te vinden in de kustvlakten waar olijfgaarden, wijngaarden en boomgaarden het historisch landschap het best bewaarden.
Opschriften tonen niet alleen aan dat Balsa tijdens de 2de eeuw een municipium was, hoogstwaarschijnlijk dankzij een gunst van keizer Domitianus (81-96), maar documenteren tegelijk het publieke leven van de antieke stad waar onder meer de gens Manlia (CIL II, 5161; CIL II, 5162) een belangrijke politieke rol speelde in de ordo decurionum en de verschillende magistraturen. De bevolking was van alle windrichtingen afkomstig. Een zekere G(aius) Blossius Saturninus die afkomstig was van het Afrikaanse Neapolis (tegenwoordig Nabeul, Tunisië) noemde zichzelf een incola Balsensis, een inwoner van Balsa (EDCS-05500115). Vanaf de 5de eeuw geraakte de stad volledig in verval. Tegenwoordig is er praktisch niets meer te zien van het antieke Balsa. Bijna heel de site van de antieke stad is privébezit, waardoor de meeste toegangen werden afgesneden en de weinige bekende en zichtbare archeologische overblijfselen min of meer verborgen blijven. Met het huidige gebrek aan bescherming en de reële dreiging van totale vernietiging is het wellicht beter dat het voorlopig zo blijft.
Archeologische opgravingen bevestigden ondertussen wel het bestaan van een oost-westweg die Balsa met Ossonoba verbond. Die laatste stad, die onder meer wordt genoemd in de routebeschrijving in het itinerarium Antonini, ligt onder het hedendaagse Faro. Romeinse overblijfselen ervan waren onder meer een tempel die werd opgegraven in de Largo da Sé. De oude stadsmuren van Faro (Muralhas de Faro) representeren het tumultueuze verleden van de stad. De Romeinen bouwden de oorspronkelijke muur rond het gebied waar zich het forum en verschillende belangrijke gebouwen situeerden. De Moren die de stad vanaf het begin van de 8ste eeuw bijna 500 jaar in handen hadden, versterkten de verdedigingswerken die tot op de dag van vandaag zichtbaar zijn. Door het centrum van het hedendaagse Tavira stroomt een rivier met twee namen, Séqua en Gilão. Tot aan de twintigste eeuw had Tavira één brug om de rivier over te steken, namelijk de Ponte Velha, de Ponte Antiga of ook de Ponte Romana genoemd. De brug bestond wellicht al in de Romeinse tijd, maar zou in zijn huidige gedaante tijdens de middeleeuwen op de antieke fundamenten zijn gebouwd. De brug is 87 meter lang en heeft zeven bogen. De Ponte Romana had, toen hij werd gebouwd, aan het begin en het einde een wachttoren. Een voorbeeld van een dergelijke wachttoren is trouwens nog te zien in Verona. Zo hielden de poortwachters zicht op wie de stad binnenkwam en konden zij ongewenste bezoekers gemakkelijker buiten houden. Door de eeuwen heen onderging de Ponte Antiga al dan niet noodgedwongen verschillende veranderingen. Sedert de zeventiende eeuw heeft de brug zijn huidige uitzicht.
Tussen de 8ste en de 13de eeuw bezetten de Moren de stad Tabira. Onder meer de Almoraviden en de Almohaden speelden in deze regio een belangrijke rol. In feite is dat niet te verwonderen gezien de strategische ligging van de stad op het kruispunt van een weg en een rivier. Tavira ontwikkelde zich toen, samen met Santa Maria al-Harum (nu Faro) en Silb (nu Silves), tot een van de belangrijkste steden in Gharb al-Andalus. Vanuit het castello boven op de heuvel konden de machthebbers zowel de omgeving als de cruciale wegen, waaronder de Ponte Antiga, perfect controleren. De bevolking van Tavira nam geleidelijk toe waaronder ook moslims uit het noorden. De muren van het castelo van Tavira tonen verschillende bouwfasen, waarvan de oudste dateert uit de periode van de Almoraviden aan het einde van de 11de eeuw of het begin van de 12de eeuw. Deze oorspronkelijke structuur werd aangepast door de Almohaden tussen 1146 en 1168. Uit deze periode dateren de belangrijkste elementen. In het gebied van de huidige citadel staat nog steeds een albarrã-toren, veelzijdig en op het zuiden gericht, die zich onderscheidt van de andere gebouwen.
Tijdens de reconquista bereikten de christelijke legers vanaf 1238 de oostelijke Algarve. Tavira werd op 11 juni 1239 of 1242 veroverd door de troepen die onder de bevel van D. Paio Peres Correia, Meester van de Orde van Santiago, stonden. Een groot deel van de bevolking kwam om het leven als vergelding voor de dood van zeven ridders van de orde. Vanuit het Castelo de Tavira heeft men een uitstekend zicht op de Igreja Santa Maria do Castelo, de moederkerk van Tavira, gelegen in de parochie Santa Maria en Santiago. Deze bevindt zich vlak bij de burcht van de stad. De kerk werd waarschijnlijk rond 1270 gebouwd toen de stad Tavira werd veroverd op de Moren op initiatief van de Orde van Santiago ter vervanging van de Arabische moskee. Vermoedelijk is deze op de fundamenten van een vroegere moskee gebouwd. Deze middeleeuwse kerk werd in 1755 verwoest door een aardbeving.