Em posição dominante sobre a foz do rio Gilão a povoação desenvolveu-se como importante porto marítimo desde a Antiguidade.

As muralhas de Tavira evidenciam diversas etapas construtivas, a mais antiga das quais remontando ao período Almorávida, em fins do século XI ou início do século XII. Embora de difícil identificação, acredita-se que tenha sido integrada por uma alcáçova no ângulo Sudeste e por um recinto amuralhado orientado no sentido Norte-Sul, ambos de modestas dimensões.

Esta estrutura inicial foi reformada no período almóada, quando adquiriu os principais elementos que chegaram até aos nossos dias, dos quais sobrevivem restos de muralhas em taipa. Na área da atual praça da República, junto ao edifício do Banco Nacional Ultramarino, foi descoberta uma antiga porta em arco de ferradura, associada, em sua origem, a uma torre defensiva. Na área da atual alcáçova ainda se conserva uma torre albarrã, multifacetada e voltada a sul, destacada das demais estruturas.

A partir da conquista pelos cristãos, uma nova etapa construtiva se sucedeu, conferindo-lhe a planta ovalada ainda hoje identificável, que, na Baixa Idade Média, atingia cerca de cinco hectares, superfície considerável para a época e que atesta a importância da povoação. Deste período são de destaque as intervenções realizadas sob os reinados de D. Afonso III e de D. Dinis, acreditando-se que datem deste último os restos identificados nos terrenos da Pensão Castelo, assim como a própria configuração original da Porta de D. Manuel, em arco quebrado ainda em estilo gótico. Na passagem para a Idade Moderna, esta porta veio a tornar-se o principal eixo de passagem entre o interior e o exterior das muralhas, razão pela qual nela se inscrevem as armas deste soberano.

Embora a primitiva ocupação humana da região remonte à pré-história, uma campanha arqueológicaempreendida em 1997, trouxe à luz um troço de muralha Fenícia datado do século VIII a.C., comprovando a existência de um entreposto ou de uma colônia aqui estabelecida por aquele povo de navegadores e comerciantes.

À época da Invasão romana da Península Ibérica, a povoação, então denominada Balsa, adquiriu importância estratégica devido à construção de uma ponte sobre o rio. Embora não hajam sido localizados vestígios materiais de uma fortificação neste período, acredita-se que um destacamento tenha guarnecido este trecho da antiga estrada romana.

Embora a pesquisa arqueológica remonte a povoação Muçulmana ao século XI, as primeiras informações escritas a seu respeito datam da primeira metade do século XII, quando era denominada at-Tabira, referindo a sua fortificação no contexto das lutas entre Almorávidas e almóadas, que levaram à submissão da povoação ao emir Almunine, em 1168.

À época da Reconquista cristã da península, as forças portuguesas atingem o leste algarvio a partir de 1238. Tavira foi conquistada em 11 de Junho de 1239 (Maio de 1240, segundo Alexandre Herculano ou mesmo 1242 segundo outras fontes), pelas forças de D. Paio Peres Correia, Mestre da Ordem de Santiago. A tradição associa a esta conquista a uma represália daquela Ordem pela morte de sete de seus cavaleiros em uma emboscada quando à caça no sítio das Antas (Freguesia da Luz).

A 9 de janeiro de 1242 (ou 1244 segundo outras fontes), Sancho II de Portugal (1223-1248) doou os domínios de Tavira e o padroado da sua igreja à Ordem de Santiago, doação confirmada em 1245 pelo Papa Inocêncio IV.

Pretextando que a cidade havia sido conquistada por uma Ordem Militar castelhana, Afonso X de Castela reclamou-a para si, vindo a impor-lhe cerco e a conquistá-la em 1252. No ano seguinte, firmou-se um tratado pelo qual Afonso III de Portugal (1248-1279) desposaria a filha de Afonso X e, caso dessa união resultasse um filho que viesse a completar os sete anos, o avô materno lhe daria como presente o Algarve. Tendo as condições desse diploma sido preenchidas em 1264, Afonso X entregou o Algarve a Afonso III por carta de 20 de Setembro, passada em Sevilha. Em função deste ato, o soberano português concedeu cartas de foral a diversas povoações algarvias, a primeiro das quais a Tavira, em Agosto de 1266.

Sob o reinado de D. Dinis (1279-1325), o castelo foi reparado e reforçado e a cerca da vila ampliada (1292), conforme inscrição epigráfica. Data desse período a ereção da Torre de Menagem. O soberano, por Carta Régia de 1303, ampliou os privilégios dos moradores, impedindo que os seus bens fossem penhorados ou vendidos excepto por dívidas com a Coroa.

À época da crise de 1383-1385, o Mestre de Avis doou o Reguengo de Tavira a Fernão Álvares Pereira, irmão do Condestável Nuno Álvares Pereira. Posteriormente, após a conquista de Ceuta, iniciado o processo dos Descobrimentos portugueses, a povoação veria a sua importância estratégica e econômica aumentar. O seu castelo, entretanto, apresentava risco de derrocada, conforme a queixa de suas gentes perante as Cortes de 1475.

Sob o reinado de Manuel I de Portugal (1495-1521), a vila recebeu o Foral Novo (1504), elevando-a à categoria de cidade em 16 de Março de 1520, entre outros importantes privilégios. É seu Alcaide-mor à época Vasco Eanes Corte-Real.

Em 1573, quando D. Sebastião (1568-1578) visita Tavira, encontram-se em progresso as obras de construção do Forte de Santo António (Forte do Rato), fronteiro à barra do rio Gilão em 1577.

Posteriormente, no contexto da Guerra da Restauração da independência, D. João IV (1640-1656) confirma todos os privilégios concedidos a Tavira por seus antecessores, determinando obras de modernização do castelo medieval, reforçando-lhe a estrutura e adaptando-o aos tiros da então moderna artilharia. A defesa da povoação será complementada, em 1672, pelo início da construção da Fortaleza de São João da Barra de Tavira, na Gomeira, fronteira à barra do rio Gilão em 1717.

No século XVIII a estrutura do castelo será severamente danificada pelo terramoto de 1755, o que certamente contribuiu para que, nos séculos seguintes o perímetro defensivo da povoação fosse desmantelado em grande extensão.

As muralhas do Castelo de Tavira encontram-se classificadas como Monumento Nacional, por Decreto publicado em 16 de Maio de 1939.