Gyrodactylus malalai sp. nov. is described from the fin surface of cichlid fishes Oreochromis niloticus (L.) and Tilapia zillii (Gervais) caught in Lake Turkana (Kenya). The new species morphologically resembles Gyrodactylus nyanzae Paperna, 1973, but can be readily distinguished by the shape of the marginal hook sickles and the size of its hamuli. The sequence data of rDNA spanning partial 18S, internal transcribe spacer 1 and 2 and the 5.8S gene is unique within GenBank. Genetically, as most similar Gyrodactylus ergensi Přikrylová, Matějusová, Musilová et Gelnar, 2009 was found (97.5%). Moreover, a specimen of G. cichlidarum from O. niloticus, and a specimen G. ergensi from Sarotherodon galilaeus (L.) were collected during sampling in Kenya. Likewise, additional sampling of O. niloticus from the Blue Nile in Sudan revealed the presence of the newly described species. These findings represent the first records of gyrodactylids in both African countries.