La tâche la plus urgente et la plus pressante lorsque Lénine sortit de l’exil était de construire le parti prolétarien révolutionnaire. Le Parti ouvrier social-démocrate de Russie (POSDR) avait été formellement créé dans un Congrès tenu en 1898 auquel participaient 9 délégations. Cependant, le Comité central élu au Congrès avait été très rapidement arrêté par la police. Bien que l’unification fût annoncée, ce Congrès ne réussit pas vraiment à unifier tous les groupes et à mettre en place une structure organisationnelle unique pour le parti. Ainsi, en 1900, cette tâche restait à accomplir.
Le plan de construction du parti avait été élaboré en détail en exil. La clé de l’unification résidait pour Lénine dans la mise en place d’un journal politique commun à toutes les organisations russes. Lénine proposa que le seul moyen d’unir politiquement et organisationnellement les cercles d’études marxistes, les groupes et les organisations dispersés était à travers un journal commun. Ce journal pourrait lier politiquement toutes les cellules de la Russie en présentant la ligne correcte et en luttant immédiatement contre toutes les déviations opportunistes. Mais en même temps, le secret qu’imposait le devoir de distribuer un journal illégal ferait de lui même naître une organisation clandestine entraînée à faire face à la répression de la police secrète russe. Lénine voulait mettre ce plan en œuvre avant la convocation d’un Congrès du Parti parce qu’il fallait d’abord vaincre les tendances opportunistes et révisionnistes qui avaient relevé la tête au cours des années précédentes.
Le plan de Lénine fut d’abord discuté et approuvé par l’Union de Lutte dans diverses villes russes et lors d’une conférence des sociaux-démocrates, organisée pour discuter de ce plan. Ses principaux associés étaient Martov et Potresov, membres du groupe central de Saint-Pétersbourg qui avaient été arrêtés et envoyés en Sibérie en même temps que lui. Le plan était de publier le journal de l’étranger, car il était trop dangereux de le faire en Russie. Lénine prévoyait également de s’unir avec le groupe Libération du Travail de Plekhanov, qui existait déjà à l’international. Le comité de rédaction devait se composer de six membres – trois du groupe Libération à l’étranger et trois en Russie – Lénine, Martov et Potresov. Après avoir tout arrangé, le premier numéro fut publié en décembre 1900.
Il s’appelait l’Iskra, ce qui signifie littéralement l’Étincelle. Son titre portait les mots des premiers révolutionnaires bourgeois russes de 1825 – L’Étincelle allumera une Flamme. L’Etincelle fut imprimé dans différents pays – l’Allemagne, l’Angleterre et la Suisse. Il n’était jamais envoyé directement en Russie, mais traversait des routes détournées jusqu’à atteindre les comités secrets de L’Etincelle en Russie. Les distributeurs avaient la tâche extrêmement difficile d’éviter la police secrète et si les trafiquants de L’Etincelle étaient arrêtés, ils étaient immédiatement exilés en Sibérie. L’Etincelle était un outil majeur pour éduquer la classe ouvrière puisque les cours des cercles d’études étaient souvent composés de lectures du journal. Les agents de L’Etincelle profitaient de toutes les occasions pour distribuer le journal ainsi que des brochures secrètes. Les journaux étaient distribués non seulement dans les usines, mais aussi dans les rues, dans les théâtres, dans les casernes de l’armée et par la poste. Dans les grandes villes, ils étaient déposés dans les rues ou sur les balcons des théâtres. Dans les cités ouvrières ils étaient distribués tard dans la nuit ou tôt le matin où ils étaient laissés en évidence dans les cours et près des pompes à eau. Après chaque opération de ce genre, appelée semis, un marquage particulier était fait sur un mur voisin afin qu’un rapport complet puisse être reçu le matin même sur l’impact du travail de la nuit. Dans les petites villes et les villages, les brochures de l’Étincelle étaient apportées dans les chariots des paysans les jours de marché et collées sur les murs. Tout cela était un travail dangereux, car être vu en possession d’une brochure se traduisait par une arrestation immédiate et la possibilité d’un bannissement en Sibérie. Les camarades impliqués dans ce travail commencèrent lentement à se constituer en une équipe de révolutionnaires professionnels sur la base de laquelle Lénine avait prévu de construire le parti prolétarien.
En ce qui concerne la structure et la composition du parti lui-même, Lénine estima qu’il devrait se composer de deux parties: a) un cercle étroit de cadres et de meneurs prolétariens, principalement des révolutionnaires professionnels, c’est-à-dire libres de toute occupation autre que le travail de parti, et devant posséder un minimum de connaissances théoriques ainsi qu’une expérience politique dans l’organisation pratique et l’art de faire face à la police tsariste. Et b) un large réseau d’organisations locales du parti et une large base de membres bénéficiant de la sympathie et du soutien de centaines de milliers de travailleurs. Alors que le processus de construction d’un tel parti procédait à l’aide de l’Etincelle, Lénine donnait une direction à ce processus à travers ses articles et ses livres. Ses livres Par où commencer ? Que faire ? et Lettre à un camarade sur nos tâches d’organisation furent particulièrement importants. Dans ces travaux, il jeta les bases idéologiques et organisationnelles du parti prolétarien. Outre les questions d’organisation, une lutte majeure menée par Lénine fut la lutte contre les économistes, qui voulaient restreindre le parti social-démocrate uniquement à la lutte économique des travailleurs. Ils avaient grandi en importance en Russie pendant l’exil de Lénine et celui-ci se rendit compte que l’économisme devait être vaincu idéologiquement avant même la convocation du Congrès du parti. Il lança ainsi une attaque directe dirigée sur ce courant dans son livre Que faire ? Lénine expliqua comment les économistes entendaient s’incliner devant la spontanéité du mouvement ouvrier et négliger le rôle de la conscience et le rôle prépondérant du parti. Il montra comment cela conduirait à l’asservissement de la classe ouvrière au capitalisme. Tout en se revendiquant du marxisme, les économistes voulaient convertir le parti révolutionnaire en un parti de réforme sociale. Lénine montra ainsi comment les économistes étaient en fait les représentants russes de la tendance opportuniste du révisionnisme de Bernstein. Le livre de Lénine, largement distribué en Russie, réussit à vaincre de façon décisive l’économisme. Il posa donc les principes qui devinrent plus tard le fondement idéologique du parti bolchevique.
La naissance réelle de la tendance bolchevique dans le POSDR eut lieu au deuxième Congrès du Parti, en juillet-août 1903. Le débat principal au Congrès portait sur la nature du parti et, par conséquent, sur les personnes qui devraient pouvoir en devenir membres. Lénine avait en tête un parti formé, efficace, professionnel et révolutionnaire, proposant que tous les membres du parti devraient travailler dans au moins l’une des organisations du parti. Martov, d’autre part, avait comme modèle les partis légaux qui existaient en Europe et qui étaient devenus communs dans la Deuxième Internationale à cette époque. Il proposa donc des critères d’adhésion souples, ce qui permettait à quiconque qui acceptait le programme du parti et le soutenait financièrement de le rejoindre en tant que membre. Il était donc prêt à accorder l’adhésion du parti à tout sympathisant du parti. Au vote sur ce point, la majorité fut avec Martov. Cependant, plus tard, lorsque certaines sections opportunistes abandonnèrent et quittèrent le Congrès, la majorité passa du côté de Lénine. Cela se refléta dans les élections au Comité central et au Comité de rédaction de l’Étincelle, qui étaient conformes aux propositions de Lénine. Cependant, les différences entre les deux groupes demeuraient fortes et se poursuivirent après le Congrès. Dès lors, les partisans de Lénine, qui avaient reçu la majorité des voix lors des élections au Congrès, furent appelés les bolcheviks (ce qui signifie majoritaires en russe). Les adversaires de Lénine, qui avaient reçu la minorité de voix, furent nommés les mencheviks (les minoritaires en russe).
Immédiatement après le Congrès, les mencheviks commencèrent à manipuler et à diviser les activités. Cela créa beaucoup de confusion. Pour corriger cette confusion, Lénine publia en mai 1904 son célèbre livre, Un pas en avant, deux pas en arrière. Il donnait une analyse détaillée de la lutte à l’intérieur du parti à la fois pendant et après le Congrès et expliquait à ce propos les principaux principes organisationnels du parti prolétarien qui, plus tard, constitueraient les fondements organisationnels du parti bolchevik. La diffusion de ce livre rallia la majorité des organisations locales du parti au côté des bolcheviks. Cependant, les organes centraux, l’organe du parti et le Comité central passèrent aux mains des mencheviks qui étaient déterminés à combattre les décisions du Congrès. Les bolcheviks furent donc forcés de former leur propre comité et de créer leur propre organe. Les deux groupes commencèrent également à se préparer séparément à l’organisation de leur propre congrès et conférence. Ceux-ci se tinrent en 1905. La scission dans le parti était complète. Les fondations avaient cependant été jetées pour la construction du véritable parti révolutionnaire – le parti prolétarien de type nouveau.