Constantino nació a finales del siglo IX o principios del siglo X, probablemente en las propiedades familiares en el tema de Capadocia. Su padre, Eudocimo Maleino, pertenecía a la poderosa familia Maleino, y su madre, Anastacia, estaba emparentada con el emperador Romano I Lecapeno (r. 920-940). Entre sus seis hermanos destacaban Miguel Maleino y una hermana que, al casarse con Bardas Focas el Viejo, consolidó una estrecha alianza con los Focas.^[1]​^[2]​^[3]​ Su hijo, Eustacio Maleino, se convirtió en un prominente general y una figura central en la rebelión contra Basilio II.^[1]​^[2]​^[4]​

Las fuentes sobre su carrera son limitadas, basándose principalmente en la hagiografía de Miguel. Como patricio, en 955 sucedió a su sobrino León Focas el Joven como strategos del tema de Capadocia, un cargo que probablemente ocupó hasta su muerte, alrededor de 968, gracias a su experiencia militar y su vínculo con los Focas (su sobrino Nicéforo II Focas fue emperador entre 963-969). Durante su mandato, participó activamente en las campañas contra los árabes, especialmente contra Sayf al-Dawla. En noviembre de 960, bajo el mando de León Focas, contribuyó a la gran victoria bizantina en la batalla de Andrassos. También se le identifica comúnmente con el «Ibn al-Mala'ini» de las fuentes árabes, derrotado por Sayf al-Dawla en Iconio en 962.^[2]​^[5]​