The Yellow-shouldered Amazon (Amazona barbadensis) is the sole parrot of the genus Amazona that inhabits only dry forests. Its population has been dropping; therefore it has been the topic of many studies and conservation efforts. However, the phylogenetic relationship of this species to potential relatives classified within the Yellow-Headed Amazon (YHA) complex are still not clear. Therefore, we used more extensive data sets, including the newly sequenced mitochondrial genome of A. barbadensis, to conduct phylogenetic analyses. Various combinations of genes and many phylogenetic approaches showed that A. barbadensis clustered significantly with A. ochrocephala ochrocephala from Colombia and Venezuela, which created the Northern South American (NSA) lineage, clearly separated from two other lineages within the YHA complex, the Central (CA) and South American (SA). Tree topology tests and exclusion of rapidly evolving sites provided support for a NSA+SA grouping. We propose an evolutionary scenario for the YHA complex and its colonization of the American mainland. The NSA lineage likely represents the most ancestral lineage, which derived from Lesser Antillean Amazons and colonized the northern coast of Venezuela about a million years ago. Then, Central America was colonized through the Isthmus of Panama, which led to the emergence of the CA lineage. The southward expansion to South America and the origin of the SA lineage happened almost simultaneously. However, more intensive or prolonged gene flow or migrations have led to much weaker geographic differentiation of genetic markers in the SA than in the CA lineage.