Constantine Maleinos (Greek: Κωνσταντίνος Μαλεΐνος) was a prominent Byzantine general of the mid-10th century.
He held the rank of patrikios and in 955 he succeeded his nephew Leo Phokas as governor (strategos) of the theme of Cappadocia.
Likely due to his experience, but also his connection to the Phokades (his nephew Nikephoros Phokas was emperor in 963–969), he occupied this important post he held for many years, possibly as late as the time of his death in circa 968.
During this time, he was active in the campaigns against the Arabs, especially the confrontations with the Hamdanid emir of Aleppo, Sayf al-Daula.
Thus in November 960 he participated, under the command of Leo Phokas, in the great Byzantine victory over Sayf at the Battle of Andrassos.