Новый арест обернулся для него полутора годами, проведенными в тюрьме и ссылке. И вновь ему удается побег: 8 февраля 1909 года, находясь в ссылке, он заболел тифом, и его должны были перевести в другой лагерь. Но общее состояние было настолько тяжелым, что сопровождавшие сочли необходимым прервать этап не менее, чем на три недели. Его под конвоем препроводили в губернский город Вологду. По истечении назначенного срока пребывания ему, несмотря на сильно ослабленное физическое состояние, удалось бежать. В июле 1909 года он, никем не узнанный, вновь прибыл в Баку. На сей раз он недолго наслаждался свободой, ибо уже через несколько недель, во время подготовки к всеобщей забастовке рабочих нефтепромыслов, его вновь арестовали и выпустили на свободу только летом 1911 года.
Многолетнее участие в революционной работе, романтически окрашенная легенда о бескорыстном — «экспроприаторе», годы, проведенные в тюрьме и сибирской ссылке, постепенно создали Кобе репутацию весьма опытного «бойца революции», человека дела и «практики», в связи с чем Ленин ввел Кобу и его земляка Орджоникидзе, также хорошо знакомого с особенностями русского подполья, в состав центрального комитета. Оба должны были участвовать в координации деятельности партии в России. Это событие существенно укрепило в нем чувство самооценки, и Коба решил, подобно Ленину, выбрать себе псевдоним, который подчеркивал бы его твердость и силу воли. С 1912 года Иосиф Джугашвили решил называться впредь не «Коба», а «Сталин».
В начале 1913 года Ленин направил его на четыре недели в Вену для того, чтобы он мог ближе ознакомиться с программой австромарксисгов. Однако он сразу отверг позицию австрийских социал-демократов, которые видели задачу своей партии в том, чтобы «сохранить национальные признаки всех наций и народностей». Уже в это время он видел высшую цель в организации пролетариата для предстоящей классовой борьбы и в сплочении рабочих всех национальностей в единой партии, возвышающейся над нациями. В этом Сталин, написавший после возвращения статью «Марксизм и национальный вопрос», смог убедить также и Ленина, который уже через несколько лет назначил его народным комиссаром по делам национальностей, сославшись на профессиональные знания Сталина в этом вопросе.
Через несколько дней после прибытия в Санкт-Петербург он по доносу шпика охранки вновь был арестован и отправлен в Костино, один из самых отдаленных лагерей под Туруханском на крайнем севере Сибири. И, наконец, в 1914 году его перевели в поселок Курейка, где температура во время долгой арктической зимы часто опускалась ниже минус сорока, а летом заключенных неописуемо донимал гнус. О побеге из этого богом забытого места на краю света нечего было и думать, поскольку до ближайшей железнодорожной станции нужно было на санях добираться более шести недель. Унылое безлюдье, долгая сибирская зима и полная оторванность от остального мира требовали большой физической и душевной стойкости, и многие из ссыльных не выдерживали. У Сталина хватило твердости и воли к сопротивлению, и он вышел живым из этого ада. Но все же он за эти годы заметно сдал, перестал интересоваться рыбной ловлей и охотой и почти не участвовал в беседах и политических дискуссиях товарищей. Яков Свердлов, который вместе со своим товарищем Суреном Спандаряиом играл руководящую роль среди трехсот товарищей по несчастью в Курейке, писал позднее жене о Сталине: «Товарищ, с которым я здесь жил, в личном отношении был просто невозможен. Мы вынуждены были воздерживаться от встреч и разговоров».
Трудности при социальной адаптации он испытал еще во время ссылки в Сольвычегодск в 1909–1910 годах. На сей раз к этому добавилась очевидная для всех потеря интереса к политике, что свидетельствовало об истинной реактивной депрессии, в которую он впал в Курейке. В благодарственном письме семье Аллилуевых, у которых он нашел убежище в Санкт-Петербурге и где его приняли как зятя, он подтвердил получение посылки и попросил прислать ему открытки, иллюстрируя свое психическое состояние следующими словами: «Природа в этой проклятой местности пустынна и безобразна; летом река, зимой снег. Вот и весь пейзаж, окружающий нас. Поэтому у меня такая идиотская тоска по пейзажам, пусть даже на бумаге». В этих строчках отчетливо проступает депрессивное настроение, причиной которого является унылость места его ссылки. Особенно удручало его то, что газеты приходили с опозданием иногда на месяцы, и он был совершенно не в состоянии получать информацию о текущих политических событиях в России.