Permaneció fiel a Alejo desde entonces, participando en la mayoría de las campañas realizadas entre 1081 y 1095 en los Balcanes.
Nicéforo Meliseno nació probablemente alrededor de 1045 en Dorilea (actual Eskişehir), en las grandes propiedades que tenía su familia en la región.
Tanto su padre como madre pertenecían a la aristocracia: su padre pertenecía al linaje de los Burtzes y su madre, a la ilustre familia Meliseno, que se remontaba al siglo VIII y que dio diversos generales importantes.
[5][6] En 1070, se unió al ejército que mandaba su cuñado el protostrator Manuel Comneno, en una campaña contra los turcos selyúcidas.
La campaña terminó en derrota cerca de Sebastea y Meliseno, junto con Manuel Comneno, fue capturado por el general turco Crisósculo.