В конце 1898 и начале 1899 годов Сталин принимает участие в сходках читательского кружка, а весной все чаще и чаще молодой Джугашвили начинает вступать в конфликт с дирекцией семинарии. В мае, после нескольких предупреждений за нарушение режима и неявку на экзамен, Сталина исключают из семинарии. Он не нашел работу, вернулся в дом матери, и лишь 28 декабря устроился в Тифлисскую физическую лабораторию и получил казенную квартиру. Теперь, имея время и работу для прикрытия, он посвятил себя нелегальной работе.
Весной 1900 года были арестованы руководители «Месаме даси», но никто не узнал о том, что 20-летний Джугашвили был одним из активных организаторов демонстрации 1 Мая. В том же году Сталин познакомился с В Курнатовским — представителем редакции «Искры», который приехал в Тифлис.
Весной 1901 года тифлисские социал-демократы снова готовились к 1 Мая. Но царская охранка уже 21 марта арестовала Курнатовского. Спустя неделю молодой Сталин перешел на нелегальное положение. Отныне в течение 16 лет он жил под различными фамилиями, скрываясь от полиции. Джугашвили стал профессиональным революционером, солдатом подпольной организации, боровшейся за власть в России.
О партийной работе Сталина в первый период его революционной деятельности имеется не слишком много достоверных данных. Став в ноябре 1901 года членом Тифлисского комитета Российской социал-демократичес кой рабочей партии, он отправился в Батуми. Здесь у него обострились отношения с членами местного партийного комитета, многие из которых были недовольны его грубостью и манерой поведения. Именно здесь Джугашвили взял себе псевдоним Коба, под которым приобрел известность в партийной среде. Коба — герой романа Александра Казбеги «Отцеубийца» — сильный, молчаливый, бесстрашный рыцарь, доблестный в бою, меткий стрелок, ловкий и изобретательный в трудных ситуациях. Но в истории Кобы, рассказанной Казбеги, Сталин обнаружил еще одно свойство, которое стало для него наиболее привлекательным: герой выступает как мститель.
5 апреля 1902 года Сталин был впервые арестован. Это случилось во время налета на конспиративную квартиру, когда там проходило заседание Батумского комитета. Год Сталин провел в батумской тюрьме, затем был переведен в Кутаиси, а осенью 1903 года отправлен по этапу в ссылку в Восточную Сибирь. В период с 1902 по 1913 год Сталин шесть раз подвергался арестам. Столько же раз его ссылали, и четыре раза ему удавалось бежать. Уже в январе 1904 года он покидает место ссылки и осенью того же года появляется в Батуми. Накануне революции 1905 года он принимал активное участие в агитации рабочих, писал листовки Коба неизменно выражал большевистские взгляды в Грузии, которая в то время считалась меньшевистской крепостью. Его работой заинтересовался Ленин, и в июле 1905 года Н. Крупская попросила Кавказский союзный комитет РСДРП прислать ей брошюру Кобы. Это был первый косвенный контакт между Сталиным и Лениным. Непосредственная встреча произошла в декабре того же года в финском городе Таммерфорсе, где проводилась I конференция РСДРП.
После конференции Сталин вернулея в Тифлис, а в апреле 1906 года отправился в Стокгольм на IV съезд РСДРП. Одним из вопросов съезда был вопрос о боевых отрядах партии. Была принята резолюция с осуждением терактов, которые все меньше носили политический характер и все больше напоминали открытые грабежи. Объектами экспроприации («эксов») являлись банки, почтовые вагоны, перевозка денег и драгоценностей. Эти акции служили укреплению материальной базы партии, увеличению ее денежных средств. Резолюция же съезда давала разрешение на проведение налетов только на склады оружия. Но, вопреки резолюции съезда, такого рода акции продолжались. Сталина даже хотели судить партийным судом за нарушение этой резолюции. Общеизвестны были его хорошие связи с двумя самыми дерзкими участниками «эксов» — Камо и Цинцадзе. Собственно, Коба и руководил проведением экспроприации на Кавказе. На V съезде РСДРП в Лондоне (май 1907 года) была вновь принята резолюция с запрещением такого рода партизанских акций. И только Ленин голосовал против этой резолюции.
После возвращения из Лондона Сталин продолжал агитационную деятельность на Кавказе, пока 25 марта 1908 года не был арестован и посажен в Баиловскую тюрьму в Баку. 9 ноября был объявлен приговор об отправке в ссылку, а в январе 1909 года этап прибыл в Вологду. Местом пребывания ссыльного Кобы был определен город Сольвычегодск. Здесь ссыльный поселился в доме Кузаковой, которая родила от Сталина сына.
Летом 1909 года Сталин бежал из ссылки, но в марте 1911 года был арестован в Баку под фамилией Меликянц и снова выслан в Сольвычегодск. С этого времени начинается длинная череда арестов и побегов Кобы вплоть до 1913 года, когда в феврале по доносу провокатора Малиновского он был арестован в Петербурге и сослан в Туруханский край.