Understanding the evolution of color in birds is important because it is used for both inter- and intra-specific communication and is often linked to other important traits including life history, behavior, immunology, and mate choice. The coppersmith barbet (Megalaima haemacephala) is widely distributed across southern Asia and many islands of the Sunda shelf and the Philippines. It occurs in two well-differentiated and completely allopatrically distributed color morphs, a red- and a yellow-headed form. We constructed a phylogeny of coppersmith barbets from both color morphs and from across their range using sequences from two mitochondrial and one nuclear loci. Strong geographical patterns were found, in which India and Sri Lanka, the Philippines and mainland tropical east Asia (TE Asia) and the islands on the Sunda shelf (Sundaland) each formed a divergent group. The red birds formed two clades within the diversity of yellow animals. Major clades were dated using a molecular clock calibrated on a larger phylogeny. The phylogeographic patterns suggest that the species likely originated in TE Asia/Sundaland and then colonized the Philippines from the south in the mid-Pleistocene, via a now extinct population on Borneo. More recently, coppersmith barbets colonized India and Sri Lanka, also from TE Asia/Sundaland. Coppersmith barbets were also likely distributed on the Malay Peninsula, but went extinct there too. The population that now inhabits this region derives from a natural recolonization of yellow morph birds about 80 years ago. The red morph evolved at least twice independently from the yellow morph in the late Pleistocene, suggesting that this change does not require very many mutational steps, and thus can arise relatively frequently, on an evolutionary timescale. This system may be ideal for further studies of the genetics of carotenoid coloration.