Two monotypic haplochromine cichlid genera (Teleostei: Cichlidae) of the Pseudocrenilabrus group are described from northern Zambia. One new genus is Palaeoplex gen. nov., with Pa. palimpsest sp. nov. as the type species, from the Luongo and Kalungwishi Rivers (Upper Congo drainage, Luapula subdrainage). It is diagnosed by a unique combination of morphological characters: (1) a fully developed infraorbital series without a distinct gap between the lachrymal and second infraorbital bone, (2) fused hypuralia 1+2 and hypuralia 3+4, (3) molariform teeth on the sagittal series of the lower pharyngeal jaw, and (4) a large maximum size. The second new genus, Lufubuchromis gen. nov., with L. relictus sp. nov. as the type species, is restricted to the upper Lufubu River catchment (Upper Congo drainage, Lake Tanganyika subdrainage). It is diagnosed by a unique combination of morphological characters: (1) a fully developed infraorbital series without a distinct gap between the lachrymal and second infraorbital bone, (2) fused hypuralia 1+2 (rarely with a visible suture) and fused hypuralia 3+4, (3) a unique male coloration pattern, i.e. deep crimson red colored areas on the anterior ventral flank parts, chest and belly and on the lower head; remaining parts of flanks and caudal peduncle bluish), and (4) a Pseudocrenilabrus blotch present in both sexes. Both new genera are compared with all remaining taxa of the Pseudocrenilabrus group and with all representatives of all other major haplotilapiine lineages.