После смерти своей первой жены 25 ноября 1907 года Коба еще более страстно отдался революционной борьбе, но в это время появились слухи о том, что он провокатор. Затем произошел очередной арест Сталина, во время которого полиции удалось захватить документы, явно свидетельствующие о «его принадлежности к запрещенному Бакинскому комитету РСДРП». Решение жандармского управления в связи с обнаружением подобного рода документов выглядит по крайней мере странным: Кобу приговорили всего к трем годам каторжных работ, причем с отправкой на прежнее место ссылки. Затем срок ссылки уменьшился до двух лет. По пути следования в Сольвычегодск, находясь в камере Вятской тюрьмы, Сталин заболел тифом, но чудом выжил. 24 июня 1909 года он совершил удачный побег из Сольвычегодска, не побоявшись вновь вернуться на Кавказ.
На свободе Сталин пребывал недолго: 23 марта 1910 года его снова арестовали. На этот раз следствие продолжалось три месяца, после чего Кобу приговорили к ссылке все в тот же Сольвычегодск. Хотя по заключению помощника начальника Бакинского жандармского управления Н. Гелимбатовского отчаянного революционера следовало наказать более строго: «Ввиду упорного его участия в деятельности революционных партий, в коих он занимал весьма видное положение, ввиду двухкратного его побега принять меру взыскания – высылку в самые отдаленные места Сибири на пять лет».
После окончания ссылки в Сольвычегодске Коба, лишенный права выезда в столицу, выбрал местом своего жительства Вологду. В это время Ленин неоднократно призывал его вернуться к активной работе, о чем сам Коба писал в одном из писем, которые, кстати, проверялись полицией. «Ильич и К° зазывают в один из двух центров (Москву или Петербург) до окончания срока. Мне же хотелось бы отбыть срок, чтобы легально, с большим размахом приняться за дело, но если нужда острая, то, конечно, снимусь». Спустя время в Департамент полиции поступило сообщение: «Как можно полагать, кавказец (имя Кобы в полиции) в скором времени выедет в Петербург или в Москву для свидания с тамошними представителями организации и будет сопровождаться наблюдением… Явилось бы лучшим производство обыска и арест его нынче же в Вологде». Но ареста не последовало, и Сталин покинул место ссылки. Уже «в 3.45 кавказец пришел на вокзал с вещами, вошел в вагон третьего класса в поезд, отходящий на Санкт-Петербург… Кавказец с означенным поездом уехал в Петербург». Полиция не спешила задерживать ссыльного беглеца, вероятно, на то были веские причины.
Для очередного побега Коба использовал так называемый железный документ – паспорт П. А. Чижикова, с которым познакомился в ссылке. Таким образом действовали многие революционеры: они покупали паспорта у местных жителей, а последние спустя какое-то время заявляли в полицию о пропаже документа. Тем временем бежавшие по поддельному документу ссыльные уже благополучно добирались до места назначения.