Diagnosis: Astatoreochromis straeleni can be distinguished from A. alluaudi by the possession of 3-4 anal spines vs. 4-7; 16-18, exceptionally 19, dorsal spines vs. 17-19 dorsal spines, rarely 16 or 20 (Ref. 126033).

Description: Small to medium sized species with moderately compressed body; snout pointed or slightly concave; eye diameter as long as, or shorter than, interorbital width (Ref. 126033). Caudal peduncle variable, ranging from somewhat longer than deep to just slightly deeper than long (Ref. 126033). Gill rakers on lower part of the anterior arch thick and stout, 8-10, last three or four reduced to small nubs (Ref. 126033). Upper and lower jaws with 1-3 inner rows of tricuspid teeth; outer series in both jaws composed of unequally bicuspid and sometimes compressed teeth, only slightly cuspidate or conical in the posteriormost part of both jaws; tooth number of outer rows increases with size, 32-56 in upper jaw and 23-44 in lower jaw (Ref. 126033). Flank scales around lateral line ctenoid, elsewhere cycloid; 28-33 longitudinal line scales, excluding the small scales on caudal fin base; cheek with 3-4, rarely 5, scale rows; scales between pectoral and pelvic fins 4-5, rarely 3 or 6 (Ref. 126033). Dorsal fin spines 16-18, exceptionally 19, soft rays 8-10; anal fin spines 3-4, soft rays 8-10; pectoral fin rays 13-14, rarely 11 or 12; caudal fin rounded (Ref. 4967, 126033). Lower pharyngeal jaw triangular, longer than, or almost as long as, wide, its width 83.3-102.8% of its length; its teeth in the lateral external rows slender and cuspidate, the central two to four rows with a mixture of molariform (anterior part of the dentigerous area) and enlarged but cuspidate teeth (Ref. 126033).

Colouration: Colour pattern of live specimens: dorsally and dorso-laterally dark grey-yellowish, orange yellowish on opercle, upper part of cheek, chest and belly; lips and lower part of cheek iridescent blue; fins orange yellowish, dorsal with red edge, more pronounced posteriorly; anal fin with 3-5 horizontal rows of bright orange-yellow ocelli; females with similar but smaller ocelli; caudal fin with black dots arranged in 6-8 more or less regular vertical rows (Ref. 126033). While general appearance remains the same, live colour pattern appears influenced by characteristics of the water in which the individuals live: Rusizi specimens caught in water with a high conductivity and muddy blackish bottom substrate in the Gatumba swamps near Lake Tanganyika during the rainy season have a darker colour pattern, specimens caught in the pools associated with the Rusizi River more to the north and in marginal vegetation of the Malagarazi River are generally lighter coloured (Ref. 126033). Colour pattern of preserved specimens: general appearance dark brown for recently preserved specimens turning lighter grey or dark grey after a couple of years of preservation; fins dark grey, edge of anal and anterior part of dorsal and pelvic fins dark brown to blackish; no mid-lateral band present; a large blackish blotch at upper posterior end of gill cover, may be vague in some specimens; a blackish vertical bar below, or behind, the eye in all recently preserved specimens, this bar may disappear in specimens kept for some time in alcohol; blackish dots arranged in interrupted horizontal rows in posterior portion of soft dorsal fin and in interrupted vertical rows in caudal fin; anal ocelli always present but less visible distally, where anal fin is dark brown to blackish (Ref. 126033).