La Phénicie établit rapidement son empire le long des plus belles côtes, puis utilise la capacité de Didon pour transférer sa capitale vers le meilleur emplacement de ville découvert.

La Phénicie a besoin de birèmes et de colons embarqués le plus tôt possible dans la partie. La combinaison de ces deux unités permet à Didon de rapidement fonder et protéger son empire de villes côtières interconnectées. Alors que vous fondez cet empire naval de marchands, choisissez un seul continent pour l'emplacement permanent de votre capitale et utilisez un cothon pour l'y transférer. En vous assurant que vos villes sur ce continent ne subissent pas de pression de la part d'autres empires de l'arrière-pays, vous sécuriserez la loyauté de vos colonies.

Aussi nommée Elissa, Didon était reine de Carthage, qu'elle fonda après avoir fui une tentative d'assassinat dans sa ville natale de Tyr, mais elle est aussi présente dans l'Énéide de Virgile. S'il est probable que Didon ait vraiment existé, de nombreux éléments de sa vie furent sans doute déformés, faisant d'elle une personnalité légendaire, mais cela ne rend l'histoire que plus passionnante encore.

Des textes de Flavius Josèphe, au Ier siècle, et de Timée, au IVe siècle, la décrivent comme la sœur de Pygmalion, roi de Tyr. Dans un récit romain plus détaillé, où elle est appelée Elissa, elle était l'épouse d'Acherbas, le haut-prêtre d'Hercule, ou plus probablement du dieu phénicien Melkart, le second homme le plus puissant de la cité. Cherchant à s'accaparer tout le pouvoir, Pygmalion fit assassiner Acherbas, et il serait allé jusqu'à tuer Didon si celle-ci n'avait pas accepté de s'exiler.

Le temple d'Archerbas possédait un trésor conséquent, qui revint à Didon. Ayant conscience que Pygmalion le lui enviait, elle décida donc de le déplacer, coffre après coffre, dans son navire, puis avant de quitter Tyr, elle les fit passer par-dessus bord sous les yeux des espions de son frère. Ce dernier en conclut qu'elle avait sacrifié son trésor, mais en réalité, elle avait fait remplacer le contenu des coffres par du sable. Ainsi, elle put se mettre en route avec le trésor de son mari décédé bien à l'abri.

Elle erra sur la Méditerranée pendant les années qui suivirent, accompagnée par sa cour fidèle. Elle finit par mettre pied à terre à Chypre, où un groupe de jeunes femmes désespérées se joignit à elle et épousa ses soldats.

Les voyageurs parvinrent sur la côte nord-africaine, où ils rencontrèrent le roi Hiarbas. Didon négocia avec lui le droit de s'installer dans la région, déclarant qu'elle ne voulait que peu de terres, "autant qu'il en pourrait tenir dans la peau d'un bœuf" ; le seigneur accepta. Didon fit alors tailler une peau en lanières extrêmement fines, et l'utilisa pour délimiter un territoire englobant une colline au bord de la côte. En l'honneur de cette leçon de topologie, la colline de Carthage fut nommée Byrsa, qui signifie en grec "peau de bœuf".

Il existe deux versions de la mort de Didon. Dans l'Énéide, Énée, personnage anachronique, s'arrêta dans la nouvelle ville de Carthage et Didon tomba follement amoureuse de lui, oubliant les vœux qui la liaient à son mari décédé. Mercure rappela à Énée qu'il était destiné à créer sa propre ville, et ce dernier quitta subitement la ville, sans même un adieu. Le cœur brisé, Didon se rendit compte qu'elle avait trahi la mémoire d'Acherbas, et elle se suicida à l'aide de l'épée d'Énée, en annonçant que Carthage serait à tout jamais l'ennemie des descendants d'Énée. Ce dernier aperçut le bûcher funéraire depuis son navire, ce qui le chagrina, mais il reprit bien vite ses activités héroïques. Ce récit romain en dit beaucoup sur la façon dont les Romains considéraient les Carthaginois, mais bien peu sur l'histoire de Didon.

Dans la seconde version, le roi Hiarbas rencontra une délégation carthaginoise et demanda la main de Didon, en menaçant de détruire la ville entière s'il essuyait un refus. Les membres de la délégation, connaissant le caractère de leur reine, n'osèrent pas lui annoncer la nouvelle, malgré le risque de guerre imminente. L'un deux prit son courage à deux mains et déclara à Didon : "Le roi Hiarbas a demandé la main d'une de nos citoyennes, et menace de détruire la ville si elle refuse." Ce à quoi elle répondit : "Si elle refuse cette demande, condamnant ainsi la ville, alors elle sera exécutée."

Quand elle réalisa que cette demande lui était destinée, Didon accepta les épousailles, mais déclara devoir d'abord briser son serment qui la liait à Acherbas avant de pouvoir épouser Hiarbas. Elle fit alors construire un immense bûcher, y déposa des offrandes, puis se jeta dans le feu, restant ainsi loyale à Acherbas et évitant du même coup de se marier à Hiarbas. Elle tint donc sa promesse en tant que reine, épouse et femme indépendante.

La chronologie du règne de Pygmalion correspond plus ou moins à la période de la naissance de Carthage, ce qui confirmerait bien l'existence de Didon, ainsi que ses errances. Il existe aussi des preuves archéologiques, même si certains chercheurs affirment qu'elles feraient référence à Tanit, une déesse phénicienne. Si Didon a vraiment vécu, parvenant à fonder Carthage tout en restant une dirigeante légitime et indépendante, alors il s'agit d'un tour de force pour cette époque de l'Antiquité. Elle est parvenue à créer une cité puissante alors qu'elle n'était qu'une réfugiée installée sur des territoires peu hospitaliers, ce qui témoigne de son talent de dirigeante et de son ingéniosité.