Неутомимый путник, он направился пешком в донские степи, затем на поля Украины и наконец к побережью Черного моря, останавливаясь по дороге, чтобы заработать несколько копеек и передохнуть. 15 июля 1891 года он проходил через одно село, рядом с Николаевым, и увидел, как посреди хохочущей толпы мужик наказывает неверную жену. Несчастная, полуголая, была запряжена в телегу, и мужик заставлял ее бежать, хлеща кнутом. Это называлось «вывод». Алексей хотел вмешаться, но был сочтен замешанным и поколочен зеваками, которые бросили его без сознания в придорожные кусты. Возвращавшийся с ярмарки шарманщик втащил его в свою двуколку и доставил в николаевскую больницу. Алексей пробыл там до выздоровления, после чего вновь отправился в дорогу, присоединился к черноморским рыбакам, затем работал на лимане, добывая соль, участвовал в сборе винограда в Бессарабии, вернулся в Одессу, где работал грузчиком, после чего продолжил свой путь, все так же пешком, направляясь в Крым и на Кубань к казакам.
Город Майкоп, когда он пришел туда, кипел и бурлил (был «чумной бунт». –
Освобожденный несколькими днями позже, Алексей продолжил свое хаотичное странствие, пройдя вдоль северного хребта Кавказских гор в направлении к Каспийскому морю, затем в обратном направлении, в берегу Черного моря. Затем он углубился в горы и от Владикавказа по Военно-Грузинской дороге дошел до Тифлиса.[22] Часть пути он проделал с неким молодым грузином, называвшим себя князем. Бездельник, лгун и трус, этот странный его спутник жил за его счет, даже обворовывал его иногда и исчезал при малейшей опасности. По прибытии в Тифлис он заверил Алексея, что в этом городе живут его богатые родственники, первой заботой которых будет устроить их обоих и накормить. Затем, оставив Алексея на улице под предлогом того, что ему нужно сбегать по одному делу, всего на несколько минут, он растворился в толпе. Стоял конец октября. Было очень холодно. Алексей напрасно дожидался шесть часов, дрожа от холода и ругаясь, возвращения своего товарища. Наконец он зашел в духан, чтобы согреться, был «нелюбезно встречен там пьяными „кинто“, немножко подрался с ними и был отправлен в участок».
Так, первая ночь пребывания Алексея в кавказской столице имела в качестве декораций облезлые стены тюрьмы. Ему грозило обвинение в подозрительном бродяжничестве и отправка обратно в Нижний Новгород, на официальное место жительства, а по пути – еще несколько тюрем. Однако во время допроса он смог назвать в качестве поручителя Началова, жившего в Тифлисе и являвшегося его начальником во времена, когда он работал на железной дороге в Добринке и Крутой. Благодаря этой рекомендации на следующий день он был освобожден.
Однако и сам Началов имел очень прогрессивные социальные идеи. Он предложил Алексею комнату в своем доме и взялся найти ему работу. Служа в управлении Закавказской железной дороги, он нашел своему протеже работу «в кузнечном молотобойцем», затем должность в одной из контор в администрации. Также он ввел его в интеллигентские круги Тифлиса, состоявшие из «политических» в ссылке. Вскоре Алексей переехал к некоему Афанасьеву, рабочему. К ним присоединились другие молодые революционеры. Их община стала центром притяжения для людей физического труда, учащихся педагогического института и семинаристов, учительниц начальной школы, учениц акушерских курсов… О своем пребывании в Тифлисе Алексей писал своему другу, Г. А. Плетневу, так: «Читаю с учениками института и семинарами. Ничему не учу, но советую понимать друг друга. С рабочими в депо железной дороги читаю и разговариваю. Есть тут один рабочий – Богатырович – хорошая фигура, с ним мы душа в душу живем. Он говорит, что в жизни нет ничего хорошего, а я говорю – есть, только спрятано, чтобы не каждая дрянь руками хватала».