Constantine was born in the late 9th or 10th century, probably in his family's estates in Cappadocia. His father was Eudokimos Maleinos, a member of the powerful aristocratic Maleinos clan, and his mother Anastaso Adralestina, a relative to the Byzantine emperor Romanos I Lekapenos (r. 920–944). He had six siblings, amongst whom the monk and saint Michael Maleinos and an unnamed sister, who married the general Bardas Phokas the Elder and cemented close ties with the powerful Phokas clan.
The sources on his career are scant, and come mostly from references in the hagiography of his brother Michael. 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. He is also usually identified with the "ibn al-Mala’ini" of Arab accounts, who was defeated by Sayf at Iconium in 962.
Constantine Maleinos had a son, Eustathios Maleinos, who became a distinguished general and one of the Byzantine Empire's wealthiest men, playing a leading role in the rebellion of Bardas Phokas the Younger against Emperor Basil II (r. 976–1025).
- Kazhdan, Alexander Petrovich, ed. (1991). The Oxford Dictionary of Byzantium. New York, New York and Oxford, United Kingdom: Oxford University Press. ISBN 978-0-19-504652-6.
- Krsmanović, Bojana (11 September 2003). "Maleinos Family". Encyclopaedia of the Hellenic World, Asia Minor. Athens, Greece: Foundation of the Hellenic World. Retrieved 15 February 2012.
- Stouraitis, Ioannis (10 October 2003). "Constantine Maleinos". Encyclopaedia of the Hellenic World, Asia Minor. Athens, Greece: Foundation of the Hellenic World. Retrieved 15 February 2012.