Еще весной 1901 года Сталин перешел на нелегальное положение. Он принимает участие в организации забастовок и демонстраций, в том числе известной Батумской демонстрации в марте 1902 года. Здесь, в Батуми, Сталин был арестован и его сослали в Восточную Сибирь, где он провел около двух лет. Уже тогда Сталин был не только практиком революции, он претендовал и на роль теоретика, во всяком случае в масштабах Закавказья. В 1900–1910 годах Сталин написал немало статей и брошюр, почти все на грузинском языке, и опубликовал их в грузинской социал-демократической печати. Работы этого периода составляют два первых тома в собрании сочинений Сталина, и большая часть из них переведена с грузинского языка лишь в 1945–1946 годах. Конечно, публикации Сталина начала века ни по количеству, ни по качеству нельзя поставить в один ряд с творчеством многих других руководителей российской социал-демократии. Но неправильно говорить и о творческом бесплодии молодого Сталина.
Революция 1905–1907 годов позволила Сталину раскрыть и некоторые другие свои способности. Именно ему было поручено провести несколько крупных террористических актов или, как их называли тогда, «эксов», то есть экспроприации. В основном это были вооруженные ограбления банков, почтовых карет, пароходов, которые допускали тогда большевики как средство для пополнения партийной кассы и закупки оружия, а также для воздействия на царскую администрацию. Особенно большую известность получило вооруженное ограбление Тифлисского казначейства, которое дало в кассу большевиков более 300 тысяч рублей. Этот «экс» провела группа боевиков, в том числе Камо (С. А. Тер-Петросян), однако в его организации и планировании приняли участие Сталин и Л. Б. Красин, руководитель «боевой технической группы при ЦК».
В 1907 году Сталин переходит на работу в Бакинскую организацию РСДРП. Участие в «эксах» делает его пребывание в Тифлисе небезопасным. К тому же в Грузии в социал-демократическом движении возобладали меньшевики, которые были решительными противниками террора. Сталин принимал участие в организации крупнейших по тем временам выступлений рабочего класса Баку, обративших на себя внимание В. И. Ленина. Несколько раз Сталина арестовывали и ссылали, но каждый раз ему удавалось бежать и возобновлять нелегальную работу на Кавказе.
Из личной жизни Сталина в этот период нужно отметить смерть его первой жены Екатерины Сванидзе после нескольких лет брака. Сталин был очень привязан к молодой жене, и ее смерть не способствовала смягчению его характера.