Eight specimens of Chelidoperca maculicauda Bineesh and Akhilesh, 2013 from the Gulf of Aden and five of C. Occipitalis Kotthaus, 1973 from the Gulf of Oman represent the first records of those species from the respective localities, and suggest a wide distribution of both along the Arabian Sea coast. Chelidoperca maculicauda was previously recorded only from its type locality on the southwest coast of India, and C. Occipitalis, only from the west coast of India, Pakistan, and Socotra Island (Yemen; type locality), western Arabian Sea. The two are compared with all currently known congeners and their diagnostic characters are reviewed.