После шести месяцев тюрьмы он был направлен в ссылку в Вологодскую губернию, куда приехал в феврале 1909 года. 24 июня он бежал. У него был фальшивый паспорт, выданный полицией Тифлиса, дата выдачи — 12 мая. Как ему удалось получить, находясь на севере, этот паспорт? Ясно, что из охранки. Он решил вернуться в Баку и Тбилиси, туда, где его должны были искать. По пути заехал в Петербург и Москву, которые были нашпигованы сыщиками.
8 месяцев спустя, в марте 1910 года, Сталин был арестован. Новый рапорт из департамента полиции Баку и Тифлиса сообщал, что «Сталин указывал своим товарищам по партии следивших за ними агентов из Баку (то есть агентов, осуществлявших его безопасность), что привело к провалу операции». Выходит, что Сталин был двойным агентом, предавая тех и этих. Полковник Еремин, только что назначенный начальником спецотдела охранки, с трудом терпел интриги этого непростого агента.
Сталин вернулся в свою вологодскую ссылку. В последний день года он отправил письмо Ленину через промежуточного адресата. В письме Сталин выступал за создание большевистского центра внутри России. Центр был создан после проведения Пражской конференции. Его возглавил агент охранки Малиновский.
Это письмо Сталина было перехвачено охранкой. Сняв копию, письмо отослали по адресу. На копии стоял гриф «совершенно секретно».
27 июня 1911 года срок ссылки Сталина заканчивался, но ему было запрещено проживание в больших городах. Он обосновался в Вологде, откуда бежал в сентябре и добрался до Петербурга. Там он был сразу арестован и возвращен в Вологду.
В это время проходила Пражская конференция, которой манипулировала охранка. Агент Малиновский начинает свое восхождение на высшие ступени партийного руководства, а Сталин по рекомендации Ленина становится членом нового ЦК партии большевиков.
29 февраля 1912 года Сталин бежит из Вологды с той же легкостью, как и прежде. Странно, что он возвращается в Баку, где социал-демократы ему не доверяют. И неудивительно — после его отъезда большинство из них было арестовано.
Сталин возвращается в Петербург и занимается выпуском ежедневной большевистской газеты «Правда», субсидируемой охранкой. Вскоре его опять арестовывают и отправляют на три года в Нарым, за 4200 километров от Петербурга. Там за драку с полицейским он предстает перед товарищеским судом и снова бежит в Петербург.
В конце 1912 года ему удается пересечь с фальшивым паспортом пять границ и добраться в Польшу к Ленину, чтобы участвовать в заседании ЦК депутатов большевистской партии в Думе. Ленин в ту пору был недоволен работой Сталина в «Правде», называя его уклонистом (так он называл выступавших за сотрудничество с меньшевиками в целях единства пролетариата).
Теперь на повестке дня стоял вопрос об отмежевании от меньшевиков. В этом была заинтересована и охранка, стремившаяся «разделять и властвовать».
Ленин решил отправить Сталина в Вену с заданием написать статью по проблеме национальностей. Теперь мы знаем из письма Сталина Малиновскому, как тот окрестил это задание — «занимаюсь всякой галиматьей». Статья им была написана, проверена и исправлена Лениным и опубликована в марте 1913 года.
В отношении генеральной линии, проводимой новой газетой, у Ленина со Сталиным не было единого мнения. Сталин выступал за обновление «Правды», Ленин выступал против и порой резко. В этот период Сталин путешествует под псевдонимом Коба. В своих воспоминаниях он пишет, что в это время им была написана статья «Ко всем рабочим и работницам России». Статья не была подписана. 12 января 1913 года, находясь в Кракове по пути из Вены, он публикует в газете «Социал-демократ» статью «Выборы в Петербурге». Она была выдержана в полемическом тоне и подписана «К. Сталин». Этот впервые появившийся псевдоним он, несомненно, долго и тщательно обдумывал. Революционеры, как и актеры, выбирают себе псевдоним со значением. Его собственная фамилия Джугашвили помогла ему в этом. На древнегрузинском диалекте «джуга» означает «железо», а «вили» — сын. Так он становится стальным человеком. Новое имя ему пришлось по вкусу, о старом он больше не вспоминает. Кобой его называют только близкие друзья, помнившие его в молодости.
Сталин возвращается в Петербург, в пасть волка — к охотящейся за ним охранке, к раздраженному Ленину и к сопернику, как и он, двойному агенту Малиновскому.
23 февраля 1913 года Сталина арестовывают в седьмой и последний раз — к его большому удивлению.
Через четыре месяца после ареста, 2 июля 1913 года, Сталина депортируют в Сибирь на четыре года. Но незадолго до истечения срока, 2 марта 1917 года император Николай II отрекается от трона. 12 марта Сталин приезжает в Петербург. 27 марта охранка распущена.