הוויקינגים, יורדי ים מוכשרים ואמיצים, נהגו להפליג מצפון אירופה אל חופי צרפת, בריטניה, אירלנד, ספרד ופורטוגל ולשדוד את ערי החוף. זמן רב לפני הופעת הוויקינגים על במת ההיסטוריה היה עם אחר, עם של יורדי ים מוכשרים ואמיצים, שעסק במסחר וב… שוד ים – אלה היו הפיניקים. הפיניקים היו עם כנעני ממוצא שמי, שהתרכז בשתי הערים, צור וצידון ובסביבה שלהם ודיבר שפה דומה לעברית.
הסיפור הראשון, המתועד, על אוצר חבוי של שודדי ים, נוגע לפיניקים. במאה השמינית לפני הספירה, נישאה בִתו של מתן הראשון, מלך צור, לבעל ספינה מוכשר, שהיה גם כוהן של האל הרקולס וגם הדוד שלה, בשם אקרבאס Acerbas או Sichaeus סיקאאוס. בת המלך, ששמה היה אליסה (מאוחר יותר התפרסמה בשם דידו), אהבה מאוד את בעלה, שנהג להפליג לכיוון אופיר ופונטוס לצורכי שוד ימי משתלם מאוד.
האח של אליסה, נשא את השם פיגמליון (לא הפסל המפורסם שהתאהב ביצירתו) וברבות הימים ירש את מלכות אביו. האח הזה היה מאוד תאב בצע וחשק באוצרות הגדולים, עליהם שמע, שגיסו צבר והסתיר. האח תקף בחשאי את ספינת גיסו והרג אותו, אך בחיפוש אחר האוצרות העלה חרס, כי שודד הים הסתיר אותם במקום סודי, באי נידח.
כשנודע לאליסה על מות בעלה, נחפזה לצייד ולאייש ספינה חדשה והפליגה איתה למקום בו ידעה שהאוצרות חבויים. היא מצאה את האוצרות, אספה אותם ופשטה עם ספינתה על האי קפריסין וחטפה משם חמשים בחורות צעירות. אליסה תכננה להמשיך להפליג מערבה, כל הזמן מערבה, עד שתגיע מעבר לעמודי הרקולס (מצר גיברלטר), ל"איי המתים", מקום, שעל פי הדת שלה, היה משכן יורדי הים שמתו. שם, באיי המתים, קיוותה להתאחד שוב עם בעלה האהוב.
המלחים לא השתוקקו כל כך להגיע למחוז חפצה, לכן שכנעו אותה לעגון על חופי צפון אפריקה, כדי להצטייד במים טריים ובמזון. במקום העגינה פגשו הפיניקים את המלך המקומי, יארבאס, שחשק באליסה. המלחים רצו להישאר במקום ולהקים עיר וביקשו לקנות את הקרקע הדרושה לשם כך. יארבאס השיב, שיתן להם את הקרקע תמורת הקפריסאיות החטופות ואליסה, אותה יקח לאישה. אליסה סירבה והייתה מוכנה לשלם בזהב תמורת הקרקע. יארבאס השיב שתמורת זהב יתן לה רק קרקע שאפשר להקיף בעור של עגל אחד. אליסה הסכימה לעסקה, לקחה עור של עגל וחתכה ממנו רצועות דקות מאוד, חיברה אותן ויצרה מהן רצועה ארוכה מאוד, איתה הקיפה את הקרקע הדרושה להקמת מצודה. המצודה נקראה בשם "בירסה" Byrsa, שם שפירושו "עור של עגל". חוכמתה של אליסה רק הגבירה את רצונו של יארבאס להפוך אותה לרעייתו, אך היא לא הסכימה ורצתה להמשיך בהפלגה, כדי להגיע למחוז חפצה. המלחים התחננו לפניה, אך היא התעקשה והזכירה להם את שבועות הנאמנות שנשבעו. בשלב זה הציתו המלחים את הספינה, כדי למנוע את ההפלגה. כשאליסה ראתה את הספינה עולה באש, רצה אליה והטילה את עצמה לתוך הלהבות.
בירסה הייתה למצודה של העיר החדשה או בשפת המלחים הפיניקים, קרת חדשה, קרתחדשת, שם ששובש עם הזמן והפך ל"קרתגו". המעצמה שהתמודדה מול האימפריה הרומית.
התושבים המקומיים, שהתרשמו מאוד מנחישותה של אליסה, כינו אותה בשם "דידו", שם המבטא זאת בשפתם. משוררים וסופרים סיפרו ושרו את העלילה והמשורר הרומי ורגיליוס שינה את העלילה והוסיף סיפור אהבה נכזבת עם מייסד רומא.