הפיניקים ייסדו נמל מסחר לחוף האלגארבה בערך בשנת 1000 לפני הספירה. אנשי קרתגו הקימו את נמל חניבעל (היום העיירה פורטימאו) כ-450 שנה מאוחר יותר. הרומאים התפשטו בחצי האי האיברי במאה השנייה לפנה"ס, ואתרים ארכאולוגיים רבים מתקופה זו עדיין נמצאים באזור.

במאה החמישית לספירה היו אלה הוויזיגותים שתפסו את האזור, והחזיקו בו עד לראשית הפלישה המורית בשנת 711. המורים קראו ללאגוש זָאווַאיה, ולעיר סנטה מריה פַארַאון, היום פארו. העיירה סילְווֶש שימשה בירה תחת שלטון המורים.

הכיבוש המורי של איבריה הביא לכך שהאזור נקרא "אל-גארב אל-אנדלוס" (המערב האנדלוסי - כש"אנדלוס" הוא השם הערבי לאיבריה שתחת האסלאם).

באמצע המאה ה-12, הודות לשורת מבצעים צבאיים מוצלחים של ממלכת פורטוגל, הסתיימה האחיזה הערבית בחבל. תחת שלטון נוצרי היה "אל-גארב" לממלכת-אלגארבה. אפונסו השלישי, מלך פורטוגל קרא לעצמו "מלך פורטוגל ואלגארבה". המלך אפונסו החמישי בתורו, בעקבות כיבוש שטחים בצפון אפריקה שנתפסו כ"אלגארבה שבחוץ", לאחר 1471, נתכנה "מלך פורטוגל והאלגארבש (צורת הרבים של אלגארבה) כאן ובחוץ", ותואר זה נותר על כנו עד להכרזת הרפובליקה הפורטוגלית הראשונה ב-1910.

כמה מהמסעות הימיים שכוננו את האימפריה הפורטוגזית יצאו במאה ה-15 מאזור העיר לאגוש. משלחות התגלית הביאו לעיר תהילה ושפע. המסחר שגשג ולאגוש הייתה ב-1577 לעיר הבירה של פרובינציית אלגארבה, תואר בו החזיקה עד שנה לאחר שנהרסה ברעידת האדמה של 1755. הרעידה, שמרכזה היה בליסבון, גרמה לצונאמי שהחריב בתים ופגע בחלקים ניכרים באלגארבה. הנזק הקיף כמעט את כל העיירות והכפרים שלאורך החוף, מלבד פארו - ששוניות המחסום של לגונת ריה פורמוזה הגנו עליה.

ב-1807 נכבש האלגארבה בידי כוחות ספרדיים, אולם שנה אחר כך הפך לחלק הראשון של פורטוגל הכבושה שהשתחרר מהפולש הספרדי, במרד אוליאו.