Dictionnaire international des militant·e·s anarchistes (DIMA)Apostol ou Apostolos, PAOLIDES ou PAOLIS naquit au XIXe siècle, en Grèce selon Le Monde ou peut-être en Roumanie. Son prénom et son nom sont en tous cas caractéristiques de l’onomastique grecque.
Le 23 mai 1880, Paolides participa à la manifestation menée à Paris en hommage aux morts de la Commune. Il fut arrêté pendant la manifestation avec François Jeallot, Eugène-Joseph Fournière, Antoine Étienne, Charles Fiorini, Errico Malatesta, Balthasar Grün, Gustave Bazin, Gabriel Deville, Alexandre Hérault, Léonard Dupaix, Henri Finance, Félix Dujardin, Léon-Hubert Bastide, Alexandre Colliot et Jules-Auguste Ardouin. À cette occasion, la presse française le décrivit à la fois comme sujet roumain et comme sujet grec.
Paolides reçut un arrêté d’expulsion dans les jours suivants et fut conduit en wagon cellulaire jusqu’à la frontière belge, encore une fois avec Grün et Malatesta. À Bruxelles, il côtoya Delsaute, Malatesta, Crié, et d’autres anarchistes. Ainsi, le 1er juin, il participa à un rassemblement tenu « Aux tanneurs » à Bruxelles avec Malatesta et Crié, entre autres. Ils y auraient discuté du lieu où Cafiero serait dissimulé, et du fait que Malatesta aurait souhaité quitter le pays rapidement pour éviter d’en être renvoyé et ainsi pouvoir revenir avec Cafiero et Garibaldi. Lors de son séjour à Bruxelles, il fut hébergé chez le compagnon Chauvière, chez qui il travaillait aussi, au 11 rue du Manège - il aurait fait remarquer qu’il appréciait son hospitalité.
L’année suivante, alors qu’il était décrit comme un « ami » de Cafiero, Paolides se trouvait en Suisse comme lui. En septembre, lorsqu’il fut perquisitionné puis arrêté par les autorités à minuit dans un chalet vers Lugano, Cafiero parvint cependant à leur tenir la discussion suffisamment longtemps pour que d’autres compagnons aient le temps de détruire des preuves pouvant être compromettantes. La police suisse ne mit la main que sur des poignards, des tubes chimiques vides ou détruits et des éléments anodins. Paolides, qui se trouvait sur les lieux lors de l’affaire fut arrêté avec Cafiero puis remis en liberté le même jour que lui. Les autorités suisses finirent par accuser le groupe de planifier une tentative d’assassinat contre le roi Humbert Ier et la question de prendre des arrêtés d’expulsion envers Cafiero et Paolides fut largement discutée.
En parallèle avec ces événements, l’Égypte vivait une révolte nationaliste anti-impérialiste depuis 1879, avec la mutinerie d’Ahmed Urabi, un militaire charismatique qui lança la révolte d’Urabi (1879-1882). En 1882, les Britanniques, qui étaient déjà en large conflit avec lui, firent un ultimatum envers l’Égyptien et bombardèrent Alexandrie (juillet 1882). Cette situation, accompagnée de l’invasion pure et simple du pays, provoqua le retour en Égypte des anarchistes de la faction d’Andrea Costa qui l’avaient quittée précédemment et, surtout, un mois plus tard, l’arrivée de Paolides, accompagné de Malatesta, Cesare Ceccarelli, Gaetano Marocco (un proche d’Alessandro ?), Galileo Palla et de Giuseppe Masnada.
Leur groupe armé chercha à rejoindre Urabi, campé à Damanhour. Leur plan visait à « faire un coup en faveur de l’anarchie » après l’avoir retrouvé, c’est à dire probablement d’essayer de le convaincre d’infléchir la trajectoire de la révolte dans cette direction, et, dans une potentielle impossibilité d’y parvenir, de lancer leur propre révolte. Cependant, ils étaient coupés des lignes égyptiennes et soudanaises par l’armée britannique, qui gardait le territoire avec attention. Le groupe entreprit de nombreuses tentatives de franchir les lignes britanniques, une fois en essayant de débarquer à Aboukir par la mer, une fois par la voie terrestre à travers Ramleh, en franchissant le Nil ou enfin au travers du lac Mariout, récemment asséché, mais dont la terre était restée trop meuble pour qu’ils puissent passer, les obligeant à rebrousser chemin. À terme, ils ne parvinrent pas à rejoindre les troupes insurgées, et celles-ci furent écrasées par les Britanniques.
En décembre 1882, il reçut le droit de retourner en France avec Fiorini et Malatesta.