После двух неудачных попыток сбежать Коба сдался и к весне 1909 г., несмотря на эпидемию тифа, задержавшего перемещение арестантов, находился в ссылке в Сольвычегодске, в двадцати пяти километрах санного пути от конечной станции железной дороги в Котласе. Там он задержался ненадолго; как говорили ссыльные, убегали все, кому не лень. Коба уехал сначала в Петербург, где будущий тесть, Сергей Аллилуев, нашел ему приют у дворника (как во Франции, так и в России дворники/консьержи в качестве доверенных помощников полиции не подлежали обыску и потому могли дать беглым преступникам надежное убежище).
Летом Коба уже находился в Баку и печатал листовки. Он не виделся ни с матерью, ни с сыном, но в его жизни появилась еще одна женщина, Стефания Петровская, которая покинула родной дом в Одессе после того, как ее овдовевший отец женился снова, сошлась с одним политическим ссыльным в Сольвычегодске, влюбилась в Кобу и уехала в Баку, чтобы жить с ним.
В марте 1910 г. Коба впервые приговорил члена партии к смерти. Группа типографов отказалась работать на подпольных печатных станках. Коба объявил, что в партию вкрались предатели, и требовал, чтобы одного из них, Николая Леонтьева, вызвали на собрание и убили. Леонтьев, однако, требовал, чтоб его судили, прежде чем казнить. Кровожадные партийцы остыли, и Леонтьев остался в живых.
Через короткое время Кобу снова арестовали. На допросе Коба отрицал все и опять потребовал амнистии. Он даже отрицал, что живет со Стефанией Петровской, которая уже призналась, что она – его гражданская жена. Жандармерия в Кутаисе, Тифлисе и Баку так долго разбирала показания и улики, доказывающие, что Коба в самом деле занимался антигосударственной деятельностью, что от пожизненной сибирской ссылки он был избавлен. (Наверное, был и подкуп, так как по крайней мере один бакинский жандарм, майор Зайцев, получал деньги от местных большевиков.) К тому же Коба взял у чахоточного соседа образчик мокроты, дал взятку тюремному врачу и просил у тюремного начальства разрешения на брак с Петровской. В итоге он получил очень мягкий приговор – пятилетний запрет на пребывание в Закавказье и перевод его, как «лица, вредного для общественного спокойствия», в Вологодскую губернию. Согласие на брак было выдано слишком поздно, в тот день, когда Кобу уже отправляли на север. Коба опять очутился в Сольвычегодске без знакомых, хотя пока ему не известный, но в будущем самый верный соратник Вячеслав Скрябин (Молотов) только что уехал оттуда в Вологду. Через несколько месяцев Коба сам переехал в Вологду, и там-то они встретились.
К 1910 г. Коба уже показал себя: он мог грабить, убивать, прошел через допросы, тюрьму, ссылку. Партия теперь считала его достаточно ценным товарищем, чтобы всячески опекать и беречь. Его избрали членом Центрального комитета, единственным, кто на тот момент находился