К весне 1921 года французское правительство, убедившись, что «большевиков нельзя победить русскими или иностранными силами, опорная база которых находилась вне пределов России, и вдобавок победить с помощью солдат, которые в момент наилучшего состояния армии в Крыму на родной почве оказались не в силах защитить его от прямого нападения советских войск», прекратило помощь остаткам врангелевской армии. Она рассредоточилась по разным странам. Новосельцев снова оказался на пароходе, на сей раз французском, который держал курс в Константинополь. Стояли теплые, почти летние дни, пассажиры все время проводили на палубе и по своему обыкновению спорили. Новосельцев, как всегда, только слушал. Его внимание привлек сравнительно молодой мужчина с бородкой в пенсне, резко выделявшийся среди военных не только типично интеллигентской внешностью, но и манерой говорить. «Большевистская революция, — доказывал он, — была чудовищной исторической ошибкой, вызванной случайным стечением обстоятельств, гримасой истории. Если бы ее не было, Россия все равно пошла бы по пути демократии и прогресса. История все расставит на свои места, и Россия пойдет вместе с другими цивилизованными странами по пути демократии и прогресса. Большевизм в России доживает свои последние дни».
Он говорил складно, убедительно, как по писаному. Человека с бородкой Новосельцев видел впервые и поинтересовался у стоящего рядом худого поручика, с мрачным выражением лица слушавшего бородатого интеллигента, не знает ли он, кто этот человек. «Федоровский, — недовольно буркнул поручик. — Типичный халупник. Смотрите, как разошелся. А спросите его, где он был, когда мы краснопузых били? Из-за таких, как он, мы и проиграли. Россия не созрела для демократии. Давить нужно этих краснопузых жидомасонов. Только силой оружия можно спасти Россию от большевиков, а мы тонем в словесах».
Фамилия Федоровского Новосельцеву уже встречалась в «Информационном листке». Они познакомились здесь же, на пароходе. Новосельцева заинтересовали рассуждения Федоровского. В отличие от большинства офицеров Федоровский был противником монархии и видел будущее процветание и величие России в демократии и прогрессе. Правда, для Новосельцева осталось неясным, что именно подразумевает его новый знакомый под этими словами. Видимо, и Федоровскому он чем-то понравился, скорее всего, его самолюбию льстил неподдельный интерес, который молодой офицер проявлял к его персоне. Когда пароход пришвартовался в бухте Золотой Рог, они были почти друзьями.
В Константинополе их пути разошлись. Федоровский вынашивал планы создания собственной газеты и понимал, что в Турции, где русских эмигрантов было сравнительно мало, издание заранее обречено на провал. Он решил ехать в Софию, звал с собой Новосельцева, однако тот отказался. Он подумывал о возвращении на родину и рассудил, что легче всего уехать из Константинополя. Однако сделать это оказалось совсем не просто. Советские суда в порт не заходили, небольшие деньги, которые у него были, таяли, в Константинополе никакой работы найти не мог, да и почти ничего делать не умел, разве что воевать. В порту, правда, можно было подработать на разгрузке судов — амбалом, как здесь называли грузчиков, однако, какой из него, с покалеченной ногой, амбал…
Как-то во время скитаний по пыльным и грязным портовым улочкам с ним заговорил по-французски молодой иностранец. Новосельцев знал французский неважно, однако они друг друга поняли. Иностранец оказался помощником капитана французского грузового судна. Видимо, ему стало жаль русского офицера, своего сверстника, и он привел Новосельцева к капитану. На судне требовался электромонтер. Новосельцева, который окончил артиллерийское училище и немного разбирался в электротехнике, взяли электриком. В Марселе он сошел на берег и больше на пароход не вернулся.
Его дальнейшая судьба мало чем отличалась от судеб тысяч таких же русских эмигрантов. На чужбине сполна пришлось вкусить эмигрантского лиха: был мойщиком посуды в ресторане, закручивал гайки на конвейере автомобильного завода «Рено». По вечерам ходил на собрания союза офицеров генерального штаба и постепенно понял, что господа офицеры озабочены не столько судьбами бывшей родины, сколько своими собственными распрями и дележом эфемерных должностей. Их объединяла лишь звериная ненависть к большевикам, советской власти.
Вести с родины находились в разительном противоречии с тем, что говорилось на собраниях. Советская Россия крепла и набиралась сил. Да и сам Новосельцев, начав зарабатывать свой кусок хлеба тяжким трудом, по-иному уже смотрел на события и все реже ходил на собрания.