De regio rondom Lagos was al bewoond in prehistorische tijd, Archeologische opgravingen tonen dit aan. De oude naam van de stad -Lacohriga- wijst op een Keltische oorsprong, ongeveer 2000 voor Christus. De haven werd veel gebruikt door Foeniciers, Grieken en Carthagers en in de Romeinse tijd wordt de stad zo groot dat men een dam voor drinkwater moet bouwen en ook een brug over de rivier bij Bensafrim wordt noodzakelijk.
De eerste stadsmuren stammen uit de 10 de eeuw en werden door de Arabieren gebouwd.
In het jaar 1249 veroveren de Portugezen onder bevel van Paio Peres Correia, een kruisridder, het gebied en voegen het toe aan het nog jonge Portugese koninkrijk.
Lagos groeide gestadig en werd steeds belangrijker gedurende de heerschappij van koning Dom Afonso IV , omdat deze de muren rondom de markt liet herstellen en daar het militaire hoofdkwartier van de Algarve vestigde.
Op 5 januari 1361, onder de heerschappij van Dom Pedro I , verkreeg Lagos de status van kleine stad met een eigen rechtspraak. Toentertijd stond de stad onder het bestuur van de bisschop van Silves, die ze als geschenk gekregen had van de koning van Castela.
De Portugese ontdekkingsreizen begonnen in het jaar 1415. De vader van Hendrik de Zeevaarder, Dom João I , was toen koning. De stad was op zijn hoogtepunt, Lagos was het geografische platform voor de oorlogen tegen Ceuta en de Moren, het uitgangspunt voor de droom van een Algarve aan de andere kant van de zee. Van hier kwamen de bevelen van Infante Dom Henrique (Hendrik de Zeevaarder) aan wie later de stad geschonken word door zijn neef Dom Afonso V.
De gouden eeuw voor Lagos was de 15 de eeuw. Ongeveer 40 jaren lang was het in de haven, vooral wegens de geografische positie tegenover Afrika, een constant komen en gaan van schepen, die jarenlang bezig waren de kusten van dit continent te verkennen. Lagos was de handelsplaats voor exotische producten uit Afrika zoals ivoor, goud en zilver. Nieuwe kerken worden gebouwd en de stad ziet een groeiend aantal kooplieden en bankiers die zich hier vestigen.
João Gonçalves Zarco en Tristão Vaz Teixeira, beide geboren in Lagos, ontdekken in 1419 het eiland Madeira en in 1434 zeilt Gil Eanes rondom Kaap Goede Hoop.
Lagos werd een noodzakelijke tussenhaven voor bijna alle schepen.
Koning Dom Sebastião maakt een staatsreis naar de Algarve en word door de inwoners van Lagos zo goed ontvangen, dat hij de stad op 27 januari 1573 stadsrechten verleent. In hetzelfde jaar word de bisschopszetel van Silves naar Lagos verplaatst, nu de hoofdstad van de hele Algarve en de residentie van kapiteins, generaals en gouverneurs.
De geschiedenis van Lagos is altijd met de zee verbonden geweest. Het meeting point op de internationale routes. Het was hier dat Hendrik de Zeevaarder zijn karvelen uitrustte die de weg openden voor het tijdperk van de ontdekkingsreizen.
Wegens de grote groei van de stad waren in de 16 de eeuw nieuwe stadsmuren nodig die in de 17 de eeuw op strategische punten versterkt werden met verdedigingstorens.
De grote aardbeving in 1755 en de tsunami, die erop volgde, verwoesten een groot deel van de stad en het duurt tot het midden van de 19 de eeuw totdat de conjunctuur weer opleeft, dankzij de visindustrie.
Heden ten dage is Lagos een dynamische actieve stad, trots op zijn verleden.