Cheitanov, après avoir été responsable d’un poste télégraphique près de Sofia en 1886, était parti l’année suivante pour occuper un poste de télégraphiste au bureau central de Saint-Petersbourg (Russie). En août 1893, afin d’apprendre la langue française, il arrivait à Paris où il allait demeurer 28 rue Madame puis 29 Avenue des Gobelins. Ne trouvant pas d’emploi, il avait été présenté par un étudiant russe à Élisée Reclus qui l’avait alors recommandé auprès de son gendre Paul Régnier colon à Tenes (Algérie). Il gagnait alors l’Algérie et travaillait à partie de décembre 1893 comme jardinier à la ferme de Tazrout (Tenes). Il fut détenu avec d’autres compagnons travaillant à la ferme — dont Xixonnet, Tracol et Boifoux (?) — lors d’une perquisition effectuée à la ferme en janvier 1894. Il lui fut reproché de ne pas avoir fait de déclaration d’étranger et la police avait saisi dans sa chambre divers textes en langue russe et une carte de visite de Paul Reclus avec diverses adresses de compagnons.
L’arrestation avait eu lieu dans les circonstances suivantes : après la perquisition Cheitanov, Xixonnet, Boifoux (?), Tracol, un certain Lortal et Benouar ben Atoufi, tous employés à la ferme de P. Régnier, étaient venus porteurs d’un drapeau rouge, deux d’entre aux armés d’un gourdin, pour tenter de s’opposer à une nouvelle perquisition à la ferme d’André Reclus. Au moment où les gendarmes les avaient emmenés, André Reclus avait crié “Vive l’anarchie !” ce qui lui avait valu un procès-verbal. Dans la foulée la police effectua une perquisition dans une autre ferme où se trouvait le compagnon Léonce Cotinaud chez qui fut saisie une abondante correspondance. Ils furent inculpés d’outrages à magistrat et transférés à Orléansville. Le 21 juin suivant il fut condamné à 4 mois de prison et l’objet d’un arrêté d’expulsion daté du 24 mars 1894.