Phoenicians were probably the first eastern Mediterranean population to establish long-distance connections with the West, namely the Iberian Peninsula, from the final Bronze to the early Iron Age. For a long time, these colonies all over the Mediterranean Sea directly depended on an important city administration, Gadir, the most important metropolis in the Western Mediterranean. Modern archaeological excavations were discovered in Cadiz (Spain), the ancient city of Gadir, as well as possible Phoenician burial places. The purpose of the present work is the molecular study of 16 individuals, (V–IV millennium B.C, V A.D.) from several burial places found in Cadiz, attempting to disclose their maternal biogeographical ancestry. Furthermore, the determination of a possible biological link between two individuals found buried together was also an objective of this investigation. Of all the 16 analyzed individuals, eight of them produced positive results. Three main lineages were found: HV0, H and L3b. In general, the results support an Eastern origin for this set of individuals, reinforcing the theory of a Phoenician origin. Due to their historical period, in some cases, it was not possible to discard a Roman origin. Finally, the maternal kinship between two individuals found buried together was discarded.