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