Several studies have demonstrated strong population structuring over small distances in the rocky-shore mbuna cichlid fishes from Lake Malawi, suggesting the potential for allopatric speciation. However, many endemic Lake Malawi cichlids are neither mbuna, nor confined to rocky shores. Using microsatellites, we investigated the population structure in three species of the non-mbuna genus Protomelas. The rocky-shore P. taeniolatus showed high levels of population structure even over distances of less than 1 km, while the sandy-shore species P. similis showed no significant structure over distances up to 21 km. Protomelas fenestratus, which is generally found at the interface between rocks and sand, also showed low levels of population structure. Our results suggest that the model of allopatric speciation based on habitat fragmentation within the current lake basin may be equally applicable to rocky-shore non-mbuna as to mbuna, but that an alternative model is required to explain speciation among sandy-shore species as well as the deep-water and pelagic species.