1903年秋，斯大林被流放到西伯利亚东部，刑期3年。12月间，在流放地他收到了列宁的一封信。后来，斯大林回忆说：“我最初和列宁认识，是在1903年。固然，这次认识并不是经过亲自会面，而是经过互相通讯。但是这次认识给我留下了一个不可磨灭的印象，我在党内工作的整个时期中，这个印象始终没有消失过。那时我正被流放在西伯利亚……列宁的这封信虽然比较短，但是他对我们党的实际工作做了大胆无畏的批评，并对我们党在最近时期的全部工作计划做了非常明确扼要的说明。只有列宁才善于把最复杂的事情描写得这样简单和明确，这样扼要和大胆——他说的每一句话都是一颗打中目标的子弹。这封简单而大胆的短信使我更加确信列宁是我们党的山鹰。”
1904年1月5日，斯大林从流放地逃回高加索，为执行列宁的战略和策略，为实行列宁的无产阶级在革命中掌握领导权的思想而斗争。当时，由于日俄战争的爆发和革命的发展，布尔什维克和孟什维克之间的斗争尖锐起来。列宁认为，解决党内危机的办法便是召开俄国社会民主工党第三次代表大会。斯大林坚决站在列宁一边，在巡视南高加索和格鲁吉亚期间，他为巩固原有党组织，创立新的党组织，同孟什维克进行了不可调和的斗争。6月间，斯大林奉命来到巴库，解散了孟什维克的巴库委员会，组织了布尔什维克委员会，领导石油城的工人举行了有名的“十二月大罢工”。这次罢工由12月13日一直坚持到31日，获得了辉煌的胜利，工人与石油业主签订了俄国工人运动史上第一个集体合同。巴库罢工“是全俄一、二两月光荣发动的信号”，是俄国大革命风暴前夜的春雷。
以斯大林为首的南高加索布尔什维克带领南高加索的工人农民，进行了大规模的革命斗争，并很快地将此斗争与武装斗争结合起来。他们购置军火武器，训练红色部队，组织农民革命委员会，废除苛捐杂税，夺取地主的土地。列宁和布尔什维克党对这些斗争全面支持。俄国社会民主工党第三次代表大会听取了南高加索代表团的报告之后，根据列宁的提议，通过了特别决议，向高加索的无产阶级和农民致敬，并号召各地党委采取最积极的办法，广泛传播高加索的革命经验，支援他们的斗争。
在领导南高加索革命运动的同时，斯大林还从事艰巨的理论工作，他发动和组织了大批的出版物，宣传马克思主义。他自己也发表了《论党内意见分歧》、《答<；社会民主党人报>；》等光辉论著，批判了反布尔什维克派别的虚伪思想和叛卖立场，捍卫了马克思主义党的基础。他维护和发展了列宁关于将社会主义意识灌输到自发的工人运动中去的思想，维护并发展了列宁关于革命理论必须与工人运动相结合的思想，以及列宁关于党的建设和党的领导作用的思想。斯大林的论著得到了列宁很高的评价。
斯大林坚决维护列宁关于武装起义是推翻专制制度和成立共和国的手段的理论。他在《告公民书》中写道：“全民武装起义，这就是近年来我国政治和社会生活中全盘事件在历史上必然走向的那种必然结局。全民武装起义这就是现时摆在俄国无产阶级面前亟待解决的伟大任务！”
沙皇政府迫于人民起义的压力，于1905年10月18日颁布了所谓给予人民“自由宣言”。斯大林在第比利斯工人群众大会上讲话，公开揭露了高喊解除工人阶级武装口号的孟什维克的叛卖策略。斯大林说：“为了真正获得胜利，我们需要什么呢？为着这件事，就需要三件东西：第一是武装，第二是武装，第三还是武装。”
南高加索的布尔什维克在斯大林的领导下，积极开展武装起义的准备工作。12月上半月，在第比利斯、齐亚士雷、克里维尔、萨姆特烈加等许多城市和地区都先后爆发了武装起义，南俄大地出现了一派轰轰烈烈的革命形势。就在这一月，斯大林会见了列宁，这在俄国革命史上具有重要意义。后来斯大林回忆说：“我第一次会见列宁，是1905年12月在芬兰塔默尔福斯举行的布尔什维克代表会议上。我本来希望看见我们党的山鹰，看见一个伟大的人物，这个人物不仅在政治上是伟大的，而且可以说在体格上也是伟大的，因为当时列宁在我的想象中是一个魁梧奇伟的巨人。当我看见他原来是一个和凡人毫无区别，简直是毫无区别的、最平常的、身材比较矮小的人的时候，我是多么失望呵……”
“通常，‘伟大人物’照例是开会迟到，使会场上的人望眼欲穿地等他出现的；而且在‘伟大人物’就要出现之前，会场上的人彼此警告说：‘嘘……静一点……他来了。’我当时觉得这一套并不是多余的，因为他能令人肃然起敬。当我知道列宁比代表们到得更早，躲在一个角落里朴实地同那些参加代表会议的最平常的代表们进行最平常的谈话的时候，我是多么失望呵。老实说，我当时觉得这未免有点违背某些必要的常规。”
“后来我才明白，列宁这样朴质谦逊、这样不愿表现自己、至少是不想惹人注目、不摆架子的特点，正是他的伟大长处，正是他这种新群众的新式领袖，即人类最‘下层’普通群众的新式领袖所具有的最大长处。”
在塔默尔福斯代表会议上，斯大林做了南高加索布尔什维克组织的工作报告，并且发表了维护列宁的积极抵制第一届国家杜马（即议会）策略的演说。他被选入负责编审代表会议决议的政治委员会，与列宁一起工作。他那敏锐的观察力和干练的工作作风，给列宁留下了深刻的印象。从此以后，这两位工人阶级的领袖便建立了深厚的友谊和亲密的合作。
会后，斯大林回到高加索领导革命。“莫斯科十二月武装起义”被镇压之后，沙皇政府对布尔什维克党及其领袖列宁和斯大林进行了残酷的迫害。列宁不得不侨居国外，在那里继续领导俄国工人阶级的斗争。斯大林则在俄国坚持奋斗，常常被逮捕和流放。从1902年至1913年的11年间，斯大林先后被捕7次，被流放6次，从流放地逃走过5次。
1906年至1907年间，斯大林在领导革命斗争的同时，发表了一系列卓越的论文，总标题是《无政府主义还是社会主义？》。在这些论文里，斯大林维护和发展了马克思主义党的理论基础——辩证唯物论与历史唯物论，深刻地指出社会主义革命与无产阶级专政的必然性和迫切性，以及新式的无产阶级政党领导的绝对必要性。斯大林依据这些理论，成功地领导了巴库工人的斗争。后来，列宁写道：“1908年内，在有大量罢工者的省份里，居于首位的是巴库省，参加罢工的有4.7万名。他们是群众性的政治罢工的代表！”
1912年2月间，斯大林在沃洛格达流放地得到了布拉格代表会议的消息。在这次代表会上，孟什维克被驱逐出党，布尔什维克由一个政治集团发展为独立的俄国社会民主工党。这是一个新型的党，列宁主义的党，它对俄国革命的发展具有决定的意义。列宁和斯大林为建立这个新型的无产阶级政党，进行了巨大的思想工作和组织工作。列宁所著《做什么？》一书，为建党做了思想上的准备；《进一步，退两步》一书，为建党作了组织上的准备；《社会民主党在民主革命中的两个策略》，是党在政治上的准备；《唯物主义与经验批判主义》，则是党在理论上的准备。
1912年1月的布拉格代表会议，选出了党的布尔什维克中央委员会。列宁、斯大林、奥尔忠尼奇则、斯维尔德洛夫等人当选为中央委员。为了加强党对俄国革命实际工作的领导，会议决定成立以斯大林为首的俄国中央局。尽管当时斯大林未到会，并被流放着。
1912年2月29日，斯大林在党组织的帮助下，再次从沃洛格达流放地逃了出来。他负责领导布尔什维克党中央委员会俄国局的工作，为实现布拉格代表会议的决议而斗争。他视察了俄国各个重要地区。在南高加索，他冒着被沙皇走狗逮捕的危险，击败了孟什维克的破坏，取得了维护党性、反对取消派的胜利。
1912年5月，斯大林受党中央和列宁的委托，具体组织了《真理报》的创刊工作。他领导制订了《真理报》的编辑方针，亲自编辑创刊号，实际上是这家报纸的第一任总编辑。在两年半内，《真理报》曾被沙皇政府封闭过8次，但它以新的名称继续出版，成了宣传群众、组织群众的有力武器。后在纪念《真理报》十周年时，斯大林写道：“1912年的《真理报》，奠定了布尔什维克1917年胜利的基础。”斯大林所著《马克思主义与民族问题》于1913年春发表。它是布尔什维克党在战前国际舞台上对民族问题发表的重要论著，被称为“布尔什维主义关于民族问题的理论和纲领宣言”。
1913年2月23日，斯大林在为《真理报》募捐时被捕。列宁闻讯，立刻写信给《社会民主党人报》编辑部：“我们的被捕情况是很严重的。柯巴被抓走了……柯巴幸而写完了一篇关于民族问题的长文章。很好！要为真理而战，反对崩得和取消派的分裂主义者和机会主义者。”
斯大林被监禁五个月之后，于1913年7月2日被流放到西伯利亚北部的图鲁汉斯克地区，期限4年，受尽了罕见的磨难。但是坚强如钢的斯大林，不屈不挠，巧妙地与列宁和党取得了联系，坚持斗争，顽强工作，并写了许多重要文章。
在斯大林流放期间，第一次世界大战爆发了，战争给人民带来了严重的灾难。俄国40％的男子被征当兵，大片土地荒芜，许多工厂停工，人民饥寒交迫。俄军在战争中又屡遭失败，德军占领了波兰、波罗的海沿岸和白俄罗斯的大片地区，广大群众对沙皇政府日益不满。
此时，斯大林根据同志们送的雅号，自称“柯巴·斯大林”。
在布尔什维克党的领导下，工人首先起来斗争。1914年后半年，发生过70次罢工，参加人约3.5万；1915年，罢工超过千次，参加者达50万；1916年罢工达1500起，参加者超100万。在工人运动的影响下，士兵们也展开了反战斗争。1916年10月，当法庭审判反战水兵时，在彼得格勒党委会的领导下，13万工人举行罢工抗议，迫使政府不敢判处水兵死刑。
列宁的革命理论，动员了千百万人民群众。1917年2月中旬，彼得格勒的普梯洛夫工厂开始罢工，其他工厂纷纷响应。到24日，罢工工人已达20万，他们上街游行，高呼“打倒沙皇！打倒战争！面包！”2月26日，布尔什维克号召举行总起义，成立临时政府，工人们积极响应，士兵也转向起义。到27日晚，已有6万多士兵转到起义方面来。起义工人和士兵很快就取得了胜利，逮捕了沙皇的大臣和将军，释放了政治犯，并在当晚举行了彼得格勒工人士兵代表苏维埃第一次代表大会，宣布推翻沙皇统治。胜利消息，不翼而飞，其他城市和前线士兵相继起义。统治俄国达300年之久的罗曼诺夫王朝终于被革命推翻，史称“二月革命”。
然而，孟什维克和社会革命党人在苏维埃中窃取了领导权。他们同国家杜马（议会）中的资产阶级代表达成协议，决定成立以李沃夫大公为首的资产阶级临时政府。克伦斯基等小资产阶级社会革命党人也加入了临时政府。列宁在国外揭露了这个临时政府的性质。他说：“这个新政府并不是偶然凑合起来的一群人。这是已经上升到执掌俄国政权地位的新阶级，即资本主义化的地主和资产阶级的代表人物。”
二月革命后，俄国出现了两个政权，即资产阶级临时政府和苏维埃并存的局面。1917年3月12日，斯大林从西伯利亚流放地回到彼得格勒，参加和领导布尔什维克党中央委员会和彼得格勒委员会的工作，并受党中央委托领导党中央机关报《真理报》。
为了指导革命斗争，斯大林在《真理报》上发表了许多文章，宣传党的决议和理论。在第一篇文章《论工兵代表苏维埃》中，斯大林提出了一项重要任务：巩固苏维埃并普遍成立苏维埃，以作为人民革命政权机关的工兵代表中央苏维埃为首，把它们互相联系起来，进行统一的斗争。斯大林在《论战争》一文中，拥护列宁变帝国主义战争为国内战争的口号，号召俄国劳动人民“撕下帝国主义的假面具”，“使现在这次战争不可能再打下去”。
1917年4月3日，列宁经长期流放生活后回到了彼得堡，斯大林率工人代表团热烈欢迎。4月4日，列宁在布尔什维克大会上作了战争和革命的报告，阐明了《四月提纲》，这是党争取从资产阶级民主革命过渡到社会主义革命的天才计划。斯大林在解释、宣传列宁《四月提纲》方面做了很多工作，发表了《论临时政府》、《土地归还农民》等许多文章。