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

Description: Small to medium-sized species with moderately compressed body; dorsal head profile fairly steeply sloping, straight or decurved, becoming concave in large individuals (Ref. 126033). Mouth horizontal or slightly oblique; jaws equal anteriorly or lower somewhat projecting; posterior tip of maxilla reaching, or almost reaching, vertical to anterior orbital margin; gill rakers short and stout, 7-10, generally 8-9, on the lower limb of the first gill-arch (Ref. 126033). Flank scales around lateral line ctenoid, elsewhere cycloid; 26-32, generally 29-32, longitudinal line scales, excluding the small scales on caudal fin base; cheek with 3-5 series of scales; scales between pectoral and pelvic fins 4-6, rarely 3 (Ref. 126033). Dorsal fin spines 17-19, rarely 16 or 20, soft rays 7-8, occasionally 6 or 9; anal fin spines 4-7, soft rays 6-8, rarely 9; pectoral fin rays 13-14, rarely 15; caudal fin rounded (Ref. 126033). Posteriormost teeth in outer row of upper jaw unicuspid; in small specimens, outer row teeth unequally bicuspid and relatively stout, occasionally only stout unicuspid teeth in small specimens, becoming a mixture of weakly bicuspid and unicuspid in large specimens; 28-48 outer row teeth in upper jaw and 20-42 outer row teeth in lower jaw with numbers increasing with size, 1-2, occasionally 3, inner rows of small tricuspid or occasionally unicuspid teeth in both lower and upper jaws (Ref. 126033). Lower pharyngeal jaw triangular, longer than, or almost as long as, wide, its width 78.1-108.5% of its length; lateral teeth in the posterior rows slender and cuspidate, the central two to four, occasionally six, rows with a mixture of molariform (anterior part of the dentigerous area) and enlarged but cuspidate teeth (Ref. 126033).Specimens from Lake Victoria have a more massive lower pharyngeal jaw and a greater proportion of molariform teeth compared to the similarly sized specimens from other lakes and rivers in the Victoria basin (Ref. 126033).

Colouration: Colour pattern of live specimens: anteriorly and dorsally grey yellowish, posterior-ventrally, grey greenish to bluish; a dark band, continuous with lachrymal stripe, runs obliquely backwards through, or a little behind, the eye to near the gill opening; lower jaw faint grey bluish; fins grey yellowish, dorsal fin somewhat darker and with blackish spots on soft part, caudal fin with similar spots, pelvic blackish distally, anal fin of specimens larger than 80 mm standard length with 2-3 horizontal rows of bright orange-yellow ocelli, in specimens less than 80 mm standard length anal ocelli may be absent or hardly visible (Ref. 126033). Colour pattern of preserved specimens: general appearance greyish-brown to brown, lighter ventrally; five or six dark transverse bars often interrupted ventrally on the flanks; no mid-lateral band present; a vertical or posteriorly directed, blackish bar below the eye, runs to posterior corner of mouth, occasionally extending onto lower jaw; blackish dots arranged in interrupted horizontal rows on soft dorsal fin and in interrupted vertical rows on caudal fin, these are strongly marked in large males; edge of fins dark to blackish, anal ocelli in males, when present dark grey (Ref. 126033).