Trotsky, qui était déjà marié en Russie et avait eu deux enfants de ce premier mariage, épouse Natalia Sedova à Paris en 1903. Ils déménagent dans un nouvel appartement, non loin de celui occupé par Natalia, 46 rue Gassendi.

Lors de son deuxième séjour à Paris, après la parenthèse de Genève, Natalia l'initia à la vie parisienne. Lui-même en écrit : « Je pris connaissance de Paris beaucoup plus attentivement que je n'avais étudié Londres. Ce fut sous l'influence de N.-I. Sedova. J'étais né et avais été élevé à la campagne, mais c'est à Paris que je me rapprochai de la nature. C'est là aussi que je me trouvai mis en présence de l'art véritable. J'avais autant de mal à comprendre la peinture qu'à aimer la nature. » 

Trotsky, le « non-fractionnel ». Quelques mois plus tard, lors du Deuxième Congrès du POSDR qui se tint à Bruxelles puis à Londres à l'été 1903, après avoir soutenu Lénine lors des premiers débats, Trotsky vota à la surprise de tous avec les mencheviks lors du débat sur la composition du parti. Lénine voulait la voir limitée aux marxistes révolutionnaires. Durant les années qui suivirent, jusqu'au début de la guerre en 1914, la relation entre les deux révolutionnaires resta difficile. Trotsky employait sa verve polémique pour attaquer les bolcheviks et essayer de rallier les fractions sur des positions unitaires. Il ne fut jamais vraiment proche des mencheviks, préférant agir en autonome pendant les années qui ont précédé la guerre. Durant la révolution de 1905, il se distingua et fut élu à la tête du Soviet de Pétersbourg.
Arrêté et condamné à la déportation à perpétuité en 1907, il s'évada en janvier 1907 et participa à Londres au Cinquième Congrès du POSDR. Puis, en octobre 1907, il s'installa à Vienne où il édita le magazine "Pravda". En 1910, suite aux décisions du Plénum du CC du parti de janvier, la Pravda devint l'organe du parti et les bolcheviks nommèrent Kamenev à son Comité de rédaction.