A primeira atestação árabe conhecida de ṭabíra deve-se ao geógrafo al-Idrisi, que a referencia como al-qaríya 'povoado rural'. A alcaria, que fazia parte do território de Cacela, está atestada na década de 60 do  século XII como um hisn, uma povoação fortificada que assegurava a defesa do território dele dependente (Khawli 2003). No século XIII, constitui-se como uma taifa rebelde contra os almóadas, sob cujo governo se desenvolve como cidade amuralhada AlgarbRot. 

Conquistada em 1239 por D. Paio Peres Correia, comendador da Ordem de Santiago, o castelo de Tavira é doado àquela ordem em 1242 por D. Sancho II.  D. Afonso III recupera-a para a coroa, concedendo-lhe foral em 1266 e outro, específico para a população moura, em 1269. D. Manuel I concede-lhe foral novo em 1504 e eleva-a a cidade em 1520.