The Canary Islands have become a model region for evolutionary studies. We obtained 1.8 Kbp of mtDNA sequence from all known island forms of the endemic lizard genus Gallotia and from its sister taxon Psammodromus in order to reanalyze phylogenetic relationships within the archipelago, estimate lineage divergence times, and reconstruct the colonization history of this group. Well-supported phylogenies were obtained using maximum parsimony and Bayesian inference. Previous studies have been unable to establish the branching pattern at the base of the tree. We found evidence that G. stehlini (Gran Canaria) originated from the most basal Gallotia node and G. atlantica from the subsequent node. Divergence times were estimated under a global clock using Bayesian Markov Chain Monte Carlo methods implemented by three different programs: BEAST, MCMCTREE, MULTIDIVTIME. Node constraints were derived from subaerial island appearance data and were incorporated into the analyses as soft or hard maximal bounds. Posterior node ages differed slightly between programs, possibly due to different priors on divergence times. The most eastern Canary Islands first emerged just over 20 mya and their colonization appears to have taken place relatively quickly, around 17-20 mya. The subsequent node is consistent with cladogenesis due to colonization of Gran Canaria from the eastern islands about 11-13 mya. The western islands appear to have been colonized by a dispersal event from Lanzarote/Fuerteventura in the east to either La Gomera or one of the ancient edifices that subsequently formed Tenerife in the west, about 9-10 mya. Within the western islands, the most recent node that is ancestral to both the G. intermedia/G. gomerana/G. simonyi and the G.galloti/G. caesaris clades is dated at about 5-6 mya. Subsequent dispersal events between ancient Tenerife islands and La Gomera are dated at around 3 mya in both clades, although the direction of dispersal cannot be determined. Finally, we show that G. galloti is likely to have colonized La Palma more than 0.5 Ma after emergence of the island 1.77 mya, while G. caesaris from the same clade may have colonized El Hierro very soon after it emerged 1.12 mya. There are tentative indications that the large-bodied endangered G. simonyi colonized El Hierro around the same time or even later than the smaller-bodied G. caesaris. This study demonstrates the effectiveness of Bayesian dating of a phylogeny in helping reconstruct the historical pattern of dispersal across an oceanic archipelago.