A taxonomic revision of the cichlid genus Astatoreochromis is presented. Eighteen meristic and 23 morphometric measurements were taken on 185 individuals, including type specimens. While fin counts separate populations from the Lake Victoria region (Astatoreochromis alluaudi) from those of the Rusizi and Malagarazi rivers in the Lake Tanganyika basin (A. vanderhorsti and A. straeleni respectively), clear differentiation was not detected between the latter two. Mann-Whitney U-tests on specimens of comparable size from the two Tanganyika populations revealed significant differences in specimens < 75 mm SL, mainly in pharyngeal jaw proportions, but also in some other measurements on the head and body. However, these differences were not detected in specimens > 75 mm SL and Astatoreochromis vanderhorsti is herein considered a junior synonym of A. straeleni. A redescription of the two valid species of Astatoreochromis, A. alluaudi and A.straeleni, is provided.