Après son enfance, passée à Constantinople, le jeune Nikolaos Vitalidis, fils d'un portefaix, s'engage à Alger, le dans Légion étrangère française sous le nom de Victor Marie Vitalis. Il sert comme simple légionnaire affecté au 2e régiment de la Légion étrangère. Le , il participe au combat de l'oued Isly.
Il est nommé au grade de caporal le . Cité à la suite du combat de Yahya ben Taled le , il est nommé caporal fourrier le et sergent fourrier le de la même année. Sergent à l'issue du premier contrat, il retourne à Constantinople.
Rengagé comme 2e classe, le au 1er régiment étranger, il reprend rapidement ses galons, et est promu sergent-major le et accède à l'Épaulette (galon d'officier) à titre étranger le .
Il fait campagne en Algérie, puis en Crimée. Cité à la bataille d'Inkerman, il est blessé par balle à la cuisse à Sébastopol. Il est promu au grade de lieutenant le . De retour en Algérie le , il est affecté au 2e régiment étranger et prend part, le à la bataille d'Icheriden pendant laquelle il est blessé d'une balle à la jambe droite. Mais son esprit vif, son réalisme, son don pour les langues (Vitalis parlait couramment grec, bulgare, russe, turc, arabe et français) et sa propension à critiquer l'incurie et les mauvaises décisions lui attirent l'inimitié du maréchal Bazaine.
De retour en métropole, il est affecté au 75e régiment d'infanterie de ligne puis il est muté le au 2e régiment de grenadiers de la Garde, prestigieux corps d'élite et enfin au 4e régiment de zouaves, unité qui le mène au siège de Paris en 1870 au commandement d'un bataillon avec le grade de chef de bataillon pour compter du . Il est à Metz lors de la capitulation du maréchal Bazaine, mais parvient à s'évader et rejoindre les troupes défendant la capitale. Son unité s'illustre au combat de Villiers en s'emparant de deux canons prussiens, les deux seuls pris à l'ennemi pendant le siège de Paris.
La fougue du bataillon et de son chef est récompensée par la promotion du chef au grade d'officier de la Légion d'honneur. Après la défaite, il retourne en Afrique du Nord et sert successivement au 4e régiment de zouaves puis au 17e régiment provisoire d'infanterie et enfin au 117e régiment d'infanterie de ligne.
Assombri par la défaite, il décide de prendre sa retraite en 1875 et de retourner dans son pays natal, pour s'y occuper de la propriété familiale.
La première guerre des Balkans (1877-1878) entre la Turquie et la Russie provoque la réunion du Congrès de Berlin. Les puissances participant au congrès ont à nommer, pour « aider » le sultan à administrer la Roumélie orientale (province turque à majorité bulgare), un gouverneur civil et un gouverneur militaire, devant être de religion chrétienne, mais non bulgares afin de ne pas favoriser le détachement de la Roumélie de l'Empire et son rattachement à la Bulgarie nouvellement indépendante.
Le prince Alekou Vogoridès, descendant d'une lignée phanariote, est nommé gouverneur civil d'un commun accord par le sultan et le patriarche de Constantinople. Pour le poste de gouverneur militaire, le chargé d'affaires français propose le chef de bataillon Vitalis qui présente l'avantage, par rapport aux candidats soutenus par les autres puissances, de connaître les langues locales et d'être à la fois sujet de l'Empire ottoman et orthodoxe.
Sa candidature est retenue et, compte tenu de l'importance du poste qui lui est attribué, le Congrès l'élève au grade de général et le sultan lui confère le titre de pacha. Arrivé à Philippopoli, capitale de la province, il organise une milice destinée à maintenir l'ordre après le départ des troupes russes. Il reste en Roumélie orientale pendant deux ans, gère efficacement le pays mais lutte contre les intrigues russes et bulgares qui visent à faire absorber la province par la Bulgarie. Il réprime violemment les comitadjis bulgares qui luttent pour l'unité de leur pays, mais comprend vite que la séparation voulue par le Congrès de Berlin n'est pas tenable et, remplacé après deux années de proconsulat à Philippopoli, il revient à Constantinople où le Sultan le prend comme aide de camp et le nomme commandant de l'armée turque et pacha de Constantinople, chargé de réorganiser la gendarmerie ottomane. Il est promu au grade de général de division. Dans ce nouveau poste, il se heurte encore une fois à l'inertie du personnel dont il doit changer radicalement la manière de servir.
La Roumélie orientale proclamera son union à la Bulgarie en 1888 et celle-ci sera reconnue en 1908. Vitalis Pacha prend sa retraite en 1890, à la tête d'une grande fortune, et meurt à Constantinople en 1899, entouré de son épouse et de ses neuf enfants légitimes (la légende lui en attribue une trentaine d'autres, illégitimes, partout où il est passé, du Mexique à la Crimée en passant par Paris).
Brillant, courageux et efficace, mais opportuniste dépourvu de tout idéal, Vitalis Pacha, malgré sa collection de médailles, est oublié en Grèce (il a servi l'Empire Ottoman), en Turquie (il était membre du milliyet des Roumis orthodoxes, et il a combattu contre des musulmans en Algérie), au Mexique (c'était un étranger membre d'un corps d'occupation) et encore plus en Bulgarie; c'est encore la France qu'il a le mieux servie et qui se souvient le mieux de sa mémoire.
