Die Anwesenheit des Menschen ist in Portugal seit dem Homo erectus belegt. Vom Neandertaler sind die Spuren durch einen Lagerplatz bei Vilas Ruivas im Distrikt Castelo Branco bereits deutlicher. Muschelschalenhaufen, von Archäologen Køkkenmøddinger genannt, entstanden vom Mesolithikum bis zum frühen Neolithikum durch den Verzehr von Muscheln an immer derselben Stelle. Aus diesen Muschelhaufen sind auch Bestattungen bekannt. Ab etwa 5000 v. Chr. ist der Ackerbau belegt (Cardial- oder Impressokultur). Später entstanden die zahlreichen Megalithanlagen (Alcalar). Etwa 1000 v. Chr. dringen die Kelten hier ein und vermischen sich mit den Einheimischen zu Keltiberern oder Lusitaniern. Etwa zeitgleich errichteten die Phönizier erste Häfen entlang der Küste der Algarve. Die Karthager gründeten ca. 550 v. Chr. Portimão (lat. Portus Hannibalis). Im zweiten Jahrhundert v. Chr. entstanden im Zuge der römischen Besiedelung der Iberischen Halbinsel zahlreiche Villen, deren Ruinen (Abicada, Boca do Rio, Milreu-Estói, Villamoura) - vornehmlich in der Gegend von Faro und Lagos - besichtigt werden können.

Nach Eroberung durch die Goten im fünften Jahrhundert wurde die Algarve ab 711 von den Mauren eingenommen. Der arabische Name al-gharb (der Westen) erklärt sich aus der geographischen Sicht Andalusiens. Die islamische Herrschaft wurde durch die Rückeroberung durch die Christen (Reconquista) im 13. Jahrhundert beendet.

Von 1595 bis 1808 war die Algarve ein halb-autonomes Gebiet mit eigener Steuerhoheit im portugiesischen Staatsverband. Die portugiesischen Könige führten in dieser Zeit den Titel eines Königs von Portugal und Algarve.

Als 1807 Napoleon in den Norden Portugals einmarschierte, wurde die Algarve von spanischen Truppen besetzt. Diese Besetzung endete durch die Rebellion von Olhão im Jahre 1808.