Закаленный в борьбе петербургского пролетариата, Куйбышев принес в Сибирь непримиримость революционера-ленинца и большой опыт подпольной работы. Вот почему, несмотря на юный возраст Куйбышева, его избирают в состав Омского комитета РСДРП и поручают ему общее руководство пропагандистской работой.
Это доверие он полностью оправдал. С большим революционным искусством Куйбышев руководил забастовкой железнодорожных рабочих, а затем забастовкой торгово-промышленных служащих Омска. С большой революционной страстью выступал против соглашателей-меньшевиков, разоблачая их предательство и измену интересам трудящихся. В этой борьбе с меньшевиками особенно проявились ленинская непримиримость и принципиальность Куйбышева. Благодаря помощи и руководству Куйбышева омская партийная организация была очищена от меньшевиков и в ней укрепилось большевистское руководство.
За период своей работы в Омске Куйбышев неоднократно выезжал в Каинск, Барабинск и Петропавловск для организаций политических массовок и революционных кружков. Всюду он разъяснял большевистскую программу, готовил людей к борьбе с буржуазно-монархическим строем.
В то время с Дальнего Востока после русско-японской войны войска спешно перебрасывались для подавления революционного движения.
Надо затормозить продвижение этих войск к центру России, — настаивал Куйбышев, — там готовится вооруженное восстание рабочих. Для этого необходимо расстроить работу железных дорог.
Куйбышев организовал в Петропавловске забастовку рабочих железнодорожного депо.
В Омске Куйбышев впервые был арестован и привлечен к суду. Арест произошел во время Омской городской партийной конференции в ноябре 1906 года. Конференция собралась на окраине города, в маленьком домике. По первому вопросу о партийном съезде выступил докладчиком Валериан Владимирович. Только что он закончил доклад и начал говорить второй оратор, как вбежал один из товарищей, бывших во внешней охране, и крикнул:
— Мы окружены казаками!
Вслед за тем в дом ворвался исправник, а за ним полицейский пристав и казачий офицер. С револьвером в руке пристав орал:
— Руки вверх, стрелять будем!
За спинами передних товарищей, которые вынуждены были поднять руки, остальные поспешили уничтожить партийные документы и бумаги. Однако, уничтожили не все: полиции удалось захватить один экземпляр резолюции конференции, а также печать Омского комитета РСДРП и несколько прокламаций.
Арестованных заставили с поднятыми руками выйти из квартиры. По выходе их немедленно оцепил большой отряд казаков и повел в полицейский участок. Арестовано было тридцать восемь человек. Всех их поместили в маленькой комнатушке, так что они не могли не только лечь, но даже сесть. К тому же было нестерпимо душно.
— Выбить стекла! — предложил кто-то.
Куйбышев, находившийся ближе всех к окну, вышиб стекло. Холодный воздух освежил заключенных. Дышать стало легче.
— Петь! Петь! — послышалось в камере.
Чистое звучное контральто запело в ответ:
«Сижу за решеткой в темнице сырой…»
«Вскормленный на воле орел молодой», — подхватило несколько голосов.
Через несколько часов арестованных под усиленным конвоем перевели в городскую тюрьму.
— Что ты дрожишь, — обратился Куйбышев
— Нет, так — какая-то нервная дрожь…
— Нас много. Не падай духом! Жаль вот только, что у тебя дома в ящике литература осталась.
В тюрьме Валериан Владимирович был избран политическим старостой. Он вел переговоры с тюремным начальством, умело, с большим тактом и успехом защищая интересы заключенных.
Большую нравственную поддержку находили в нем молодые заключенные, еще не успевшие закалиться в борьбе. Своим участием, ласковым вниманием, советом, веселой беседой Куйбышев ободрял их.
Находясь в тюрьме, заключенные наладили связи с партийной организацией и принимали активное участие в политической жизни. Лично Куйбышев получал с воли записки в хлебе, в которых сообщались новости. В свою очередь и он посылал руководящие записки, помещая их в пустых черных бутылках из-под молока или под этикетками бутылок.
Эти связи с партийной организацией были настолько тесны, что однажды в камере для свиданий было устроено объединенное совместное заседание двух составов Омского партийного комитета: прежнего, арестованного, и вновь избранного. На этом совместном заседании были избраны делегаты на V Всероссийский партийный съезд в Лондоне (1907 года).
К заключенным приходили на свидание иногда в камеру. Куйбышев и его друзья воспользовались этим и организовали освобождение двух товарищей, только что арестованных во время избирательной кампании в Государственную думу. Арестованных переодели в платье пришедших, а пришедших оставили в камере. Два товарища ушли, а гости остались. Потом их, разумеется, должны были освободить. В наказание заключенные были заперты на замок и могли разговаривать во время свиданий лишь через решетку. По инициативе Куйбышева, в знак протеста была объявлена голодовка, в результате которой арестованные были переведены в другое место.