An unanswered question in biology is how the evolution of genome structure supports or accompanies diversification and speciation on different time scales. African cichlid fishes are a well-documented system ideal for studying rapid evolution, due to their phenotypic diversity and high number of speciation events over the last several million years. I generated two de novo genome assemblies of the riverine cichlid Oreochromis niloticus (tilapia) and the Lake Malawi cichlid Metriaclima zebra using high-coverage long-read sequencing data and anchored the assemblies to chromosomes using several genetic and physical maps, to produce two high-quality anchored references. By comparing these chromosome-scale assemblies to integrated recombination, transcriptome, and resequencing data of multiple genera and species, I identified and characterized many large novel genome rearrangement events. These rearrangements included multiple novel sex-determination inversions, several metacentric-acrocentric karyotype differences via centromere assembly and placement, and wide regions of suppressed recombination in genera- and species-level crosses of Lake Malawi cichlids. Karyotype evolution in cichlids was further analyzed with long-read sequencing, specifically revealing the complex structure and content of a highly repetitive supernumerary chromosome present in some but not all individuals of a population across a wide range of eukaryotes, including many cichlid species. These supernumerary "B" chromosomes are shown to be limited to female Lake Malawi cichlids and have a unique evolutionary history with B chromosomes present in Lake Victorian cichlids male and females. This work reveals how structural genomic changes impact a rapidly evolving clade, while providing high-quality resources for the community, a context for previous genetic studies, and a robust platform for future genome research in cichlids.