En el transcurso de su viaje por el Mediterráneo, antes de arribar a Italia, Eneas desembarca en Cartago, al norte de África, y allí, según Virgilio, se enamora de la reina Dido.
Dido era fenicia de nacimiento, de la ciudad de Tiro. Obligada a huir de su patria tras el asesinato de su esposo, estaba terminando de construir una nueva ciudad en Cartago cuando Eneas y sus hombres fueron arrastrados hasta la playa próxima. Los recibió generosamente y casi de inmediato se enamoró del troyano. Alentada por su hermana, Ana, empezó a aceptar su deseo por el extranjero y a esperar que la pidiera en matrimonio.
Un día, cuando Eneas y ella estaban de caza, se desencadenó una tormenta y ambos se refugiaron a solas en una cueva. Hicieron el amor mientras rugía la tempestad y a partir de entonces vivieron juntos como marido y mujer y Eneas actuó casi como si fuera el rey de Cartago.
Cuando llegó el mensajero de los dioses a recordarle a Eneas su deber, fundar una nueva Troya en Italia, el troyano decidió abandonar a su amada y continuar su viaje. Dido descubrió enseguida sus intenciones y le recriminó su traición. Aunque profundamente afligido, Eneas sólo pudo argumentar que los dioses le obligaban a marchar y rogarle que no hiciera su partida aún más dolorosa.
Desesperada, Dido resolvió suicidarse. Erigió una enorme pira funeraria, simulando que estaba destinado a un rito mágico para recuperar a Eneas o al menos para curarse de su amor. Tras una noche de insomnio, vio que el barco de Eneas ya había levado anclas. Maldiciéndole y rogando por la eterna enemistad entre Cartago y los descendientes del troyano, subió a la pira, cogió la espada de su amante y se infligió una herida mortal.
Eneas no escapó por completo de Dido. En su viaje a los infiernos, vio al fantasma de la reina e intentó una vez más justificar su conducta, pero Dido se negó a hablarle y volvió con el fantasma de su marido.
La leyenda de Dido y Eneas presenta estrechos vínculos con la historia política y militar de Roma: el ruego de la reina por la enemistad entre Roma y Cartago proporcionó una justificación mitológica para la guerra entre ambas ciudades durante el mandato de Anibal (218-201 a.C.)