Adaptive radiations could often occur in discrete stages. For instance, the species flock of ∼1000 species of Lake Malawi cichlid fishes might have only diverged once between rocky and sandy environments during the initial stage of their diversification. All further diversification within the rock-dwelling (mbuna) or sand-dwelling (utaka) cichlids would have occurred during a subsequent second stage of extensive trophic evolution that was followed by a third stage of sexual trait divergence. We provide an improved phylogenetic framework for Malawi cichlids to test this three-stage hypothesis based on newly reconstructed phylogenetic relationships among 32 taxonomically disparate Malawi cichlids species. Using several reconstruction methods and 1037 ultra-conserved element (UCE) markers, we recovered a molecular phylogeny that confidently resolved relationships among most of the Malawi lineages sampled when a bifurcating framework was enforced. These bifurcating reconstructions also indicated that the sand-dwelling species Cyathochromis obliquidens was well-nested within the primarily rock-dwelling radiation known as the mbuna. In contrast to predictions from the three-stage model of vertebrate diversification, the recovered phylogeny reveals an initial colonization of rocky reefs, followed by substantial diversification of rock-dwelling lineages, and then at least one instance of subsequent evolution back into sandy habitats. This repeated evolution into major habitat types provides further evidence that the three-stage model of Malawi cichlid diversification has numerous exceptions.