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