Die Anwesenheit von Menschen  im Gebiet, das die Gemeinde Alcoutim umfasst, könnte bis in das mittlere Paläolithikum zurückgehen. Jüngst wurden in der Gemeinde Pereiro archäologische Spuren aus dieser Zeit gefunden. Jedoch ließen sich erst ab dem Neolithikum (5.000 v.C. bis 3.000 v.C.) "bauende" Bevölkerungen in diesem Gebiet nieder. Zeugnis ihrer Anwesenheit sind die verschiedenen Beispiele megalithischer Monumente, die über die fünf Gemeinden verteilt zu finden sind. Prähistorische Monumente, Menhire, Tholosgräber und megalithische Grabstätten sind einen Besuch wert.

Auch bezüglich der Bevölkerungen der darauffolgenden Perioden gibt es viele Elemente, die als Nachweis der Kontinuität dienen. Die Begräbnisstätten aus der Bronze- und Eisenzeit sind ein Beispiel.

Das prähistorischen Grab der Heiligen Rita (Vila Nova de Cacela) stellt auch eines der letzten am besten erhaltenen megalithischen Zeugnisse der Region. Jüngste archäologische Arbeiten in den Jahren 2007 und 2008 ermöglichten eine Charakterisierung der architektonischen Struktur und eine erste Annäherung an die Chronologie, Charakterisierung der Landschaft, Studien der sozialen Struktur und der Beerdigungsrituale in den Gemeinden, welche dieses prähistorische Grab vor etwa 4500 Jahren gebaut und genutzt haben.

Die Römer kamen im frühen 2. Jahrhundert v. Chr. in das Gebiet, sie nutzten die Erzminen, die in einigen Teilen der Region bereits existierten. Aus dieser Zeit sind noch viele Spuren vorhanden, die uns die Existenz organisierter Gemeinschaften in familiären oder Wohungsgruppen nachweisen, vor allem in den den Küstengebieten, wo die besten landwirtschaftlichen Flächen zu finden sind. Dort findet man häufig die Spuren der römischen Präsenz. Hier übte der große Fluss des Südens - der Guadiana - eine starke Anziehungskraft aus. Über ihn breiteten sich Handelswege aus, welche das Land mit dem Mittelmeerraum verbanden.

Noch heute finden wir Spuren der römischen Orte und Siedlungen entlang des Flusses Guadiana - wie etwa im Falle von Villa Romana in Montinho das Laranjeiras, das heute eine archäologische Station und vollkommen für Besuche vorbereitet ist. Der Ort befindet sich neben der Ortschaft Montinho das Laranjeiras, etwa acht Kilometer südlich der Stadt Alcoutim. Auch fand man Spuren von Strukturen, die auf die Nutzung von Wasserversorgungssystemen hinweisen, wie Aquädukte und Stauseen, die die Bewässerung der zu kultivierenden Felder genutzt wurden, wie etwa die Ruinen des Dammes von Álamo. 

Während der römischen Besetzung behielt Baesuris, heute Castro Marim, seine Bedeutung als wichtiger Umschlagplatz der Produkte, die aus dem Mittelmeerraum stammten. Auf einer Insel gelegen, welche sie über die Mündung des Guadiana erhob und diese dominierte, kontrollierte der Ort bis zum Untergang des römischen Reiches die Routen der Schifffahrt auf dem Fluss, eine Situation, die bereits seit der Ankunft der Phönizier in diesem Gebiet im 9. Jahrhundert v. Chr. vorherrschte. 

Auch in Cacela sind zahlreiche Spuren aus der Römerzeit zu finden. Sie sind von größter Bedeutung, man fand unter anderem Tanks zur Salzlager von Fisch und Töpfereien. 

Später siedelten sich auch andere Völker auf dem römischen Gebiet an, unter anderem Alanen, Vandalen und Westgoten. 

Zu Beginn des 8. Jahrhunderts wurde die Region von den Mauren beherrscht, welche einige strategische Punkte befestigten. Dies ist zum Beispiel bei Alcoutim der Fall, wo noch heute Reste der Befestigung aus dem 8. Und 9. Jh. zu sehen sind, die auf dem Hügel von Santa Bárbara erbaut war. Diese Reste wurden als Teile eines Museums aufgenommen und können besichtigt werden. Zurzeit tragen Sie die Bezeichnung "Castelo velho" [Alte Burg] von Alcoutim. Der Bau hatte ursprünglich wohl strategisches Interesse in Verbindung mit dem Fluss Guadiana und der Kontrolle der Minenerzeugnisse, vor allem Kupfer aus lokalem Abbau.  Die fünfhundert Jahre der islamischen Herrschaft in Alcoutim hinterließen, neben dem starken toponymischen Register, bis heute fast einhundert identifizierte Orte, welche die starke Präsenz in diesem Gebiet demonstrieren.

Ein weiterer strategischer Punkt war Cacela. In Verbindung mit der Politik der Zentralisierung des Kalifen Abd-Al Rahman III (912 - 961) hatte dieser Ort ganz eindeutig militärischen Charakter, wobei der Hisn von Cacela im 10. Jahrhundert erbaut worden ist. Der Hisn war eine wichtige Struktur zum Zweck der militärischen Verteidigung, integriert in die ländlichen Routen und dem Seeverkehr zwischen dem Atlantischen Ozean und dem Mittelmeer. Diese Festung diente der Verteidigung der Küste und dem Schutz der Bevölkerung. Es gibt mehrere Zeichen und Markierungen, die dieses Volk in der Region hinterlassen hat: Sowohl hinsichtlich der Ernährung, mit der Einführung von Nüssen, Citrinen und Gewürzen bei den Gerichten der Region, als auch auf der Ebene des Vokabulars. 

In der Regierungszeit von D. Sancho II wurden die Dörfer Alcoutim, im Jahre 1240, und Castro Marim, im Jahre 1242, von den Mauren rückerobert und wurden in das portugiesische Königreich integriert. 

Mit dem Fortschreiten der Rückeroberung durch die Christen (was zwischen 1238, als Mértola erobert wurde, und der Einnahme von Ayamonte im 1239 stattfand) schien ein Rückgang der ländlichen Bevölkerung Siedlungen einherzugehen, obwohl nicht alle Orte vollkommen aufgegeben wurden. Nach der endgültigen Rückeroberung der Algarve von den Mauren und der Festigung der portugiesischen und spanischen Grenzen wurden die Prozesse der landwirtschaftlichen Besiedlung und der Befestigung der Grenzorte eingeleitet. 

Alfonso III ordnete im Jahre 1272 an, dass man Castro Marim besiedele, eine königliche Anweisung zur Besiedlung der Ortschaft, die eine militärisch wertvolle strategische Position an der Grenze zwischen den beiden Königreichen eingenommen hatte. Im Jahre 1277 erhielt Castro Marim das Gemeinderecht mit umfangreichen Privilegien, um leichter Menschen in dieses Gebiet zu locken und man errichtete im Jahre 1274 über die bereits existierenden Befestigungen die Burg mit viereckiger Struktur. Der Großteil der Bevölkerung lebte auf dem Land, aber aufgrund der strategischen Position von Castro Marim wurden aus dem Meer und dem Fluss über die Fischerei andere für die Wirtschaft wichtige Produkte gewonnen, und man handelte mit diesen Produkten mit dem Königreich der Algarve und dem benachbarten Andalusien. 

D. Dinis gab Alcoutim im 1304 das Gemeinderecht und gab den Auftrag, die Mauern und die Burg wieder zu errichten und schenkte dem militärischen Orden São Tiago den Ort. Später, am 20. März 1520, wurde das Gemeinderecht von D. Manuel I. neu erneuert. 

Auch D. Dinis erkannte die Bedeutung der geographischen Lage von Castro Marim. Der König spendet den Ort und seine Festung dem neu geschaffenen Orden Christi, von wo aus der Krieg sowohl auf dem Seeweg als auch dem Landweg gegen die Mauren Nordafrikas und die kastilische Region führen konnte. Jahre später, im Jahre 1356, wurde der Orden Christi übergeben nach Tomar verlegt. Diese Verlegung wurde als ein Zeichen für einen progressiven Prestigeverlust des Ortes gesehen, wo trotz seiner hervorragenden Lage, die Bevölkerung nicht blieb, wodurch der Ort nach und nach an entvölkert wurde. 
1371 wurde der Friedensvertrag von Alcoutim unterzeichnet, der den Erbfolgekrieg von Castela zwischen dem König von Portugal, Fernando I, und dem König von Kastilien, Henrique II, beendete. 

Im 15. Jahrhundert gewinnt die Region, und vor allem Castro Marim, mit der Zunahme der Übersee Kampagnen neue Dynamik. Dabei bildete dieser Ort  für Eroberung in Übersee einen strategischen Punkt. Angesichts seiner Nähe zu Marokko nahm Castro Marim eine Schlüsselrolle im Kampf gegen die muslimische Piraterie ein. Der Ort war nach der Restaurierung der Burg, die von D. Manuel in Auftrag gegeben wurde, ein zentraler Platz im Krieg an der Algarve . So entwickelte sich der Ort zu einem wichtigen Punkt für die Sicherheit, zu einem Fischereihafen und Handelspunkt. 

Ende des 15. Jh. wurde Alcoutim eine Grafschaft zugunsten der Grafen von Vila Real. Die Familie Meneses verwaltete diese Grafschaft bis zum 17. Jh. Zu dieser Zeit wurden ihre Güter in das Casa do Infantado (1654) [Haus des Infanten] integriert.

Doch während des Restaurationskriegs im 17. Jahrhundert und angesichts der Nähe dieses Territoriums zu Spanien war Alcoutim die Bühne militärischer Scharmützel, unter denen man das Duell im Jahre 1642 der Artillerie nennen möchte, das mit S. Lucar del Guadiana beendet wurde. Im Jahre 1661 gelang es Portugal, die Burg von San Lucar zu erobern und am 29. August 1666 besetzten die portugiesischen Truppen für einige Zeit den Ort Sanlucar. 

D. João IV. (1640 – 1656) beschloss, die Burg von Castro Marim restaurieren zu lassen und neue Befestigungsarbeiten durchzuführen und erbaute auf dem Berg von Cabeço die Festung von S. Sebastião und das Ravelin von S. António auf dem Berg Rocha do Zambujal, im Osten der Festung von S. Sebastião, die durch ihre Fortschrittlichkeit im Vergleich zu anderen Befestigungsanlagen dazu bestimmt war, die Überfahrten und über und die Fahrten auf dem Guadiana zu kontrollieren. Castro Marim wurde nach diesem Konflikt die wichtigste Festungsanlage der Region der Algarve und die wichtigste südlich von Elvas.

Das Erdbeben vom 1. November 1755 erreichte den gesamten Süden Portugals, auch die Algarve, und die Zerstörung breitete sich weit aus. Moderne Geologen schätzen, dass das Erdbeben des Jahres 1755 die Klassifizierung 9 auf der Richter-Skala erreichte. 

Cacela war stark beschädigt und wurde im  18. Jh. wieder erbaut, der Zeit, in der auch die gegenwärtige Festung entstand. Die Bevölkerung verließ nach und nach den Ort und zog in Richtung der  königlichen Straße. Etwa eine Meile entfernt, neben der Straße, die nach Vila Real de Santo António führt, und auch der aktuellen Eisenbahnlinie entstand der Ort Vila Nova de Cancela, oder auch Cacela, wie es heute genannt wird. Der alte Ort Cacela, der am Meer lag, wurde in Cacela-a-Velha umbenannt. 

Auch Castro Marim erlitt große Schäden, ein Großteil des architektonischen Erbes wurde zerstört, was dazu führte, dass die Häuser innerhalb der mittelalterlichen Mauern nicht mehr genutzt wurden. Das Dorf entwickelte sich außerhalb der Mauern weiter, ohne jedoch die Bedeutung der Jahrhunderte zurückgewinnen zu können. was auch durch die Entstehung des Ortes Vila Real von Santo António zusammen mit der Verschlammung der Flussarme beeinflusst wurde. 

Vila Real de Santo António erschien in der Regierungszeit von D. José I (1750 – 1777), als der Premierminister Marquis von Pombal im 3. Quartal des  18. Jahrhunderts. eine authentische Reform in der Wirtschaft der Algarve förderte. Man erkannte schnell, dass dringende Maßnahmen in der Region ergriffen werden müssten, einerseits um zu verhindern, dass die Spanier die Wirtschaft der Zone übernahmen, und andererseits um die reichlich vorhandenen Fischressourcen, hauptsächlich Sardinen, zu nutzen, die man in der Bucht von Monte Gordo fing. 

An der Mündung des Flusses Guadiana lag Ayamonte, eine Stadt mit in jener Zeit großer strategischer Bedeutung, und auf der anderen, der der portugiesischen Seite des Flusses, lag Castro Marim. Auf der portugiesischen Seite existierte seit der Herrschaft von D. Manuel I, genauer gesagt seit 1513, ein kleiner Fischerort, Santo António de Arenilha, der seit einigen Jahren praktisch verlassen war. Etwa drei Kilometer westlich liegt Monte Gordo, damals ein Dorf, das ausschließlich aus Fischerhütten bestand. 

Es war Marquis von Pombal, der beschloss, einen Ort zu erreichten, der den strategischen Anspruch der portugiesischen Souveränität an diesem Ende der Algarve präsentieren würde, um den Handel an der Grenze zu kontrollieren und die Fischerei zu entwickeln, was später zur Entstehung der Konservenindustrie führte. Vila Real de Santo António würde schließlich in weniger als zwei Jahren in dem Gebiet der Mündung des Guadiana fertiggestellt und im Jahre 1774 gegründet. Die geometrischen Linien des pombalinischen Urbanismus, welche die Stadt prägten, sind heute ein einzigartiges Beispiel für die Aufklärung in Portugal. 
Das neue Dorf wurde vom Thunfisch abhängig, weil seine geographische Lage und sein Hafen, in dem größere Boote vor Anker gehen konnten, begannen, zog eine beträchtliche Fischerei- und Transportflotte an. Es folgte die Installation mehrerer Konservenfabriken, in denen vor allem Thunfisch und Sardinen verarbeitet wurden. 

Was die benachbarten Dörfer angeht, so gaben Sie offensichtlich dem Willen des Marquis nach. Das Dorf Cacela verliert den Titel der Grafschaft und übergibt die Verwaltung an das neue städtische Zentrum ab; Castro Marim verliert sein Zollamt, das in den pombalinischen Ort verlegt wurde. 
Mit dem Tod des Marquis de Pombal in 1782 verliert Vila Real de Santo António den anfänglichen Impuls. 

Mit der Liberalen Revolution breiteten sich die Konflikte zwischen Liberalen und der Partei von D. Miguel de Bragança auf das ganze Territorium aus. Die letzten Konflikte wurden in Alcoutim um das 1833 / 1834 registriert, in denen die beiden Fraktionen um das Besitztum des Flusses Guadiana stritten. Es wird gesagt, dass die berühmten "Remexido" [José Joaquim de Sousa Reis] einige Einrichtungen des Ortes in Brand setzte.  Zu dieser Zeit verliert Alcoutim definitiv seine strategisch-militärische Position und wird ganz oder teilweise von den benachbarten Gemeinden übernommen. Nach der Liberalen Revolution und mit der Abschaffung der feudalen Rechte, insbesondere religiöser Orden, und den spezifischen Gesetzen zur Weizenproduktion in der Region, entstanden im Landesinneren dieser Region ausgedehnte Gebiete, in denen man sich vornehmlich der Getreidekultur wie Weizen und Roggen widmete.

Seit der zweiten Hälfte des neunzehnten Jahrhunderts, und vor allem dem letzten Quartal entwickelte sich auf eine gewisse Art und Weise ein neuer Impuls in der wirtschaftlichen Entwicklung von Vila Real de Santo António. Die Existenz von Sardinen und Thunfisch in den Gewässern der Küste der Algarve verwandelt den Ort Dorf in ein wichtiges Zentrum für die Konservenindustrie, die Fischerei und die Konservenfabriken nahmen einen Großteil der Wirtschaft des Ortes ein.

In den 50er und 60er Jahren des zwanzigsten Jahrhunderts war eine große wirtschaftliche Entwicklung in Vila Real de Santo António zu verzeichnen, nicht nur durch die Ausweitung der Konservenproduktion für Thunfisch und Sardinen, sondern vor allem durch die großen Fänge von Sardellen in Marokko. Mit der Änderung der Fanggebiete von Sardellen und Sardinen begann in der zweiten Hälfte der 60er Jahre eine starke Krise in der Fischerei und der Fischkonservenindustrie. Während der Krise im Bereich der Fischerei, der Fischkonserven und des Handelshafens von VRSA fand gleichzeitig die Ausweitung des Tourismus statt.