В Луганске он впервые вступил в постоянное общение с социал-демократами. К тому времени они приобрели в городе определенную опору и влияние. Первый социал-демократический кружок в Луганске возник еще в 1900 году, и организаторами его были соратник В, И. Ленина по «Союзу борьбы за освобождение рабочего класса» В. А. Шелгунов и его друг К. М. Норинский. Основа, заложенная ими, оказалась весьма прочной, и после отъезда организаторов кружок не только не распался, но и расширился, стал успешно вести пропаганду среди рабочих.
Успеху способствовало то, что луганские социал-демократы внимательно прислушивались к идеям ленинской «Искры». В ноябре 1902 года, еще до появления Воротаинова на заводе Гартмана, под воздействием «Искры» возникает Луганский комитет РСДРП. Луганск стали навещать екатеринославские социал-демократы, они доставили литературу, помогали деньгами. Удалось впервые в Донбассе наладить выпуск «Летучего листка».
Размах социал-демократической агитации не мог не встревожить власти. Трижды за первую половину 1903 года полиция провела аресты среди луганских социал-демократов, и большинство активистов движения оказались, по терминологии полицейских, «изъятыми». Это не могло окончательно сорвать работу социал-демократов, но положение их было сложным: сохранилось лишь два кружка, и в них всего лишь 25 человек. К тому же, по свидетельству Ворошилова, «организация в это время носила характер еще не определившийся, в смысле фракционности». Формально она входила в «Союз горнозаводских рабочих», где было сильно влияние «экономистов», и это сказывалось на работе. Представитель этого союза на II съезде РСДРП адвокат И. Мошинский (Львов) оказался в лагере меньшевиков и по возвращении со съезда повел неистовую борьбу против В. И. Ленина и решений съезда.
Вот в это время, в октябре 1903 года, Клим Ворошилов стал членом РСДРП. Надо напомнить, что вступление во всякую противоправительственную организацию было тогда очень опасным делом, а особенно в РСДРП. Это могло повлечь за собой арест, ссылку, а в некоторых случаях — и каторгу. Социал-демократы, спасаясь от слежки и возможных провокаций, строго конспирировались. Не существовало и не могло существовать ни списков участников организации, ни партийных билетов, ибо обнаружение их при аресте было бы несомненной и неопровержимой уликой. Вся работа, в том числе и прием новых членов, основана была на доверии к новому товарищу, и проверялся он ежедневно своим поведением, самим делом. В то же время среди ленинцев всегда царила строжайшая сознательная дисциплина, ею и была сильна партия, в значительной степени благодаря ей большевики в конечном счете одержали победу.
Заводской мастер ошибался — Клим Ворошилов был дисциплинированным и в политике. Охотно и искренне подчинившись партийной дисциплине, он вскоре стал требовать соблюдения ее от других и бороться за нее. Мы можем уверенно сказать, что уже в первые месяцы своего пребывания в РСДРП Ворошилов выступал, действовал как большевик, ленинец.
Разобраться во фракционных взаимоотношениях внутри партии молодым рабочим было не просто, но сама логика происходящего, логика борьбы, помогала им понять, что правильный путь указывают большевики. Ворошилова, склонного всегда (и тогда уже, и позднее) к решительным и энергичным действиям, влекло в ряды большевиков, так как ему претили нерешительность, расплывчатость, характерные для мелкобуржуазной тактики меньшевиков.
Ворошилов и его товарищи сумели сориентироваться в тонкостях фракционной борьбы и определить свою позицию, став на сторону большевиков. Луганский комитет одним из первых начал борьбу с меньшевизмом. 20 ноября 1903 года на партийной конференции в Луганске была отвергнута меньшевистская резолюция, а в начале следующего года тамошние социал-демократы порвали с меньшевистским комитетом Донецкого союза. Луганская организация РСДРП становится на революционный путь и к лету 1904 года, по свидетельству Ворошилова, «определяется как большевистская».
Заслуга самого Ворошилова в этом несомненна. Ужо с первых шагов он делается заметным среди товарищей-партийцев, а вскоре становится и одним из вожаков луганской большевистской организации. О характере и разнообразии его обязанностей в 1904–1905 годах можно судить по простому их перечислению. Он не только учится в кружке, но и сам обучает других. Он превосходный агитатор и пропагандист, он любит и умеет говорить с рабочими, а они его хорошо понимают и верят ему. На рабочих «массовках» Ворошилов — постоянный оратор. Он пишет, редактирует и распространяет листовки. Он же их печатает, сначала на гектографе, а затем участвует в организации подпольной типографии. Он привлекает в партию новых людей, и рекомендованные им кандидаты всегда заслуживают доверия. Наконец, с 1904 года он стал членом луганского социал-демократического комитета.