Во всех подразделениях Всевобуча появились энтузиасты физкультурно-спортивного движения. Новое направление работы было закреплено в официальных документах Всевобуча, поддержано его печатью. Актив его округов и участков повсеместно развернул пропаганду физкультуры и спорта, а главное, взяв на себя роль организаторов, вышел с конкретными предложениями о постановке физкультурно-спортивной работы, адресовав их местным партийным, советским, комсомольским, профсоюзным организациям, руководителям фабрик и заводов. Н. И. Подвойский вошел с соответствующими предложениями в Наркомздрав, Наркомпрос и другие ведомства, в профсоюзы, Центральный Комитет комсомола. Не везде и не сразу его поняли и поддержали. Появились даже разговоры о «дон-кихотстве», о «чудачествах» Подвойского — мол, есть задачи и поважнее. Но на начинание Всевобуча охотно отозвалась молодежь. Вскоре появилась и первая ласточка: открыл свою спортивную площадку Русско-кабельный завод в Москве. Начались занятия физкультурой и с всевобучистами.

Так, весной 1920 года усилиями Н. И. Подвойского при поддержке ЦК РКСМ, Наркомпроса и Наркомздрава Всевобуч дал первоначальный толчок развитию массового физкультурно-спортивного движения в стране.

Сразу же возник дефицит инструкторов. Сначала к военно-учебной работе было привлечено более 17 тысяч бывших унтер-офицеров старой армии. Они удовлетворительно справлялись с военно-инструкторскими обязанностями, но квалифицированно вести воспитательную работу в нужном направлении не могли. В поисках выхода Н. И. Подвойский встретился с чемпионом России 1915 года выдающимся спортсменом Я. Ф. Мельниковым. Яков Федорович охотно согласился помочь Всевобучу и, кроме того, познакомил Н. И. Подвойского с другими известными спортсменами. Агитировать Николай Ильич умел. Вскоре работать во Всевобуче пришли конькобежцы П. и В. Ипполитовы, гребец Б. Астафьев, лыжники В. Григорьев и В. Серебряков, легкоатлеты А. Бирзин и А. Шульц, тяжелоатлеты А. Бессонов и А. Бухаров, боксер А. Харлампиев и другие. Они стали прекрасными педагогами-инструкторами, настоящими энтузиастами развития физкультуры и спорта, опорой Н. И. Подвойского в этом нелегком тогда деле. Боксер А. Харлампиев настолько загорелся идеей массовой физкультуры, что на долгие годы стал одним из ближайших помощников Николая Ильича. Он разделил с ним не только радость достижений, но и горечь поражений и неудач, которых оказалось более чем достаточно на их тернистом пути. Н. И. Подвойскому, хотя и с большим трудом, но все же удалось добиться перевода во Всевобуч и опытных спортсменов-любителей из частей Красной Армии.