Несмотря на свои саркастические замечания в адрес Соколовской, Лев на самом деле смещался в сторону социал-демократии. Среди молодежи постепенно распространялось недовольство самодержавием, и она все сильнее вдохновлялась марксистскими идеями. Что касается Льва, то он, вероятно, поддался обаянию марксизма потому, что конкретная программа действий сочеталась там с напряженной интеллектуальной дискуссией. Это был именно тот диалог между силовыми решениями и идеологией, которым будет отмечена его жизнь в течение последующих десятилетий.

В 1897 г. Лев с отличием окончил реальное училище и ненадолго переехал в Одессу, где жил у дяди, раздумывая об изучении математики в университете. Но его неудержимо тянуло в политику. В Одессе он «заводил случайные знакомства с рабочими, доставал нелегальную литературу, давал уроки, читал тайные лекции старшим ученикам ремесленного училища». Вскоре он вернулся пароходом в Николаев и вновь поселился в саду Швиговского.

В своих воспоминаниях Троцкий пишет об одном случившемся в начале 1897 г. ужасном происшествии, которое всполошило молодежь по всей России. Совершила самосожжение молодая курсистка, находившаяся под политическим арестом в Санкт-Петербурге, в печально известной Петропавловской крепости. Студенты вышли на улицы с протестами, и в результате многие были арестованы и сосланы в Сибирь. Теперь Лев был полон решимости выйти за рамки горячих споров о политической доктрине. Переполняемый гневом и энтузиазмом, он был готов сделать первые конкретные шаги в противостоянии царскому режиму: организовать рабочих Николаева. В то время в городе было около 10 000 рабочих и квалифицированных ремесленников. Он взял свой первый псевдоним – Львов – и стал сближаться с рабочими, приглашая их небольшими группами на тайные собрания, где обсуждалась подпольная политическая литература, которую Лев с единомышленниками доставали или производили сами. Примерно две сотни рабочих ему удалось убедить вступить в новую организацию, которую он назвал «Южно-русским рабочим союзом». В ее составе были слесари, столяры, электротехники, портнихи и студенты. Спустя годы Троцкий вспоминал свой первый успех с характерным для себя воодушевлением. «Рабочие шли к нам самотеком, точно на заводах нас давно ждали, – писал он в своих мемуарах. – Не мы искали рабочих, а они нас». В деятельность организации оказалась вовлечена и Александра Соколовская, которая, судя по всему, согласилась забыть о прежних обидах и работать плечом к плечу со своим младшим товарищем, несмотря на его несносный характер.

Лев с головой окунулся в работу. Союзу был нужен свой печатный орган, что-то типа афиши или листовки; это подчеркнуло бы самостоятельность организации и помогло привлечь рабочих на ее сторону. Лев взялся за это предприятие, назвав свою газету «Наше дело». В отсутствие пишущей машинки он аккуратно «писал прокламации или статьи, затем переписывал их печатными буквами». На изготовление каждой страницы могло уходить до двух часов. «Иногда я в течение недели не разгибал спины, отрываясь только для собраний и занятий в кружках», – позднее вспоминал он. Используя примитивный гектограф, пожертвованный одним состоятельным сторонником, он мог производить от 200 до 300 экземпляров каждого номера.

Постепенно жизнь Льва обретала узнаваемые черты. Его революционная активность и профессиональная деятельность в качестве журналиста и издателя покоились на его твердой убежденности в силе слова. Становясь старше и проходя через мучительные жизненные потрясения, он неизменно будет возвращаться к одной основополагающей идее: необходимости учредить газету – подпольную или легальную – или хотя бы писать для нее статьи в расчете на внимание и влияние, которое, как он надеялся, это ему принесет. В Николаеве он с удовлетворением отмечал заметный эффект, который его газета производила среди рабочих города. По революционным меркам Лев с товарищами старались поставить перед рабочим довольно скромные цели повышения зарплат и сокращения рабочего дня. Кроме того, в его прокламациях рассказывалось об условиях труда на городских верфях и фабриках, о злоупотреблениях работодателей и государственных чиновников.