Сразу же возник дефицит инструкторов. Сначала к военно-учебной работе было привлечено более 17 тысяч бывших унтер-офицеров старой армии. Они удовлетворительно справлялись с военно-инструкторскими обязанностями, но квалифицированно вести воспитательную работу в нужном направлении не могли. В поисках выхода Н. И. Подвойский встретился с чемпионом России 1915 года выдающимся спортсменом Я. Ф. Мельниковым. Яков Федорович охотно согласился помочь Всевобучу и, кроме того, познакомил Н. И. Подвойского с другими известными спортсменами. Агитировать Николай Ильич умел. Вскоре работать во Всевобуче пришли конькобежцы П. и В. Ипполитовы, гребец Б. Астафьев, лыжники В. Григорьев и В. Серебряков, легкоатлеты А. Бирзин и А. Шульц, тяжелоатлеты А. Бессонов и А. Бухаров, боксер А. Харлампиев и другие. Они стали прекрасными пе-дагогами-инструкторами, настоящими энтузиастами развития физкультуры и спорта, опорой Н. И. Подвойского в этом нелегком тогда деле. Боксер А. Харлампиев настолько загорелся идеей массовой физкультуры, что на долгие годы стал одним из ближайших помощников Николая Ильича. Он разделил с ним не только радость достижений, но и горечь поражений и неудач, которых оказалось более чем достаточно на их тернистом пути. Н. И. Подвойскому, хотя и с большим трудом, но все же удалось добиться перевода во Всевобуч и опытных спортсменов-любигелей из частей Красной Армии.
Привлечение спортсменов не решало до конца кадрового вопроса — их было слишком мало. Но у Н. И. Подвойского уже был наработан опыт решения кадровых проблем. Ему были известны два способа их решения: развертывание сети собственных курсов и привлечение общественников. Он в полной мере использовал оба способа. Уже в следующем, 1921 году на различных курсах Всевобуча было подготовлено 20 тысяч инструкторов при общей их потребности в 25 тысяч. Кроме сети краткосрочных курсов, в Москве действовали Высшие организационные курсы и гордость Николая Ильича — двухгодичная Главная военная школа физического образования.
Н. И. Подвойский очень скоро убедился, что без опоры на науку массовое спортивно-физкультурное движение правильно организовать невозможно. Всевобуч установил тесные деловые связи с Государственным институтом физической культуры имени П. Ф. Лесгафта, созданным в Петрограде в трудном 1919 году. По инициативе и при самом активном участии Николая Ильича на базе Главной военной школы физического образования только в 1920 году было проведено несколько научных конференций. Сам он изучил десятки книг по физиологии, психологии, организации спортивного движения в России и в зарубежных странах. В ею рабочих блокнотах начала 20-х годов часто встречаются записи о встречах с профессорами института имени П. Ф. Лесгафта, учеными-медиками, в них множество выписок из специальной литературы, журналов. По этим записям видно, с каким упорством и с какой целеустремленностью он подымался на тот уровень знаний, который был необходим для компетентного руководства физкультурно-спортивным движением в стране.
Повернув в несколько месяцев работу Всевобуча в новое русло, Н. И. Подвойский, верный ленинскому принципу проверки исполнения, отправился в округа и на участки, чтобы лично убедиться в том, что дело пошло. Он объехал 22 губернии. Практически везде он сталкивался, с одной стороны, с бедностью, нехваткой средств н оборудования и связанными с этим трудностями, с другой — с энтузиазмом и энергией, изобретательностью и находчивостью инструкторов и всевобучистов по преодолению этих трудностей. Это радовало Николая Ильича. Ведь, прилагая гигантские усилия к тому, чтобы раз-верпуть в условиях разрухи спортивное и физкультурное движение, Н. И. Подвойский многим тогда казался оторванным от жизни мечтателем. Но он твердо стоял на реальной почве.
Учитывая бедственное положение страны, Николай Ильич добивался самого широкого распространения таких видов спорта, которые не требовали больших затрат материальных средств, имели военно-прикладное значение, а главное — могли и должны были стать массовыми: ходьбы, бега, прыжков, лазания по канату, метания, плавания, велосипедного спорта, туризма, лыжного бега. Николай Ильич не звал к достижению рекордов, которые являются уделом единиц, а ставил задачу оздоровления и физического воспитания миллионов и миллионов людей. Особенно пропагандировались футбол, баскетбол, лапта, городки.
— Спортивные игры требуют инициативы и импровизации, — доказывал он. — Они воспитывают коллективизм, заставляют играть на команду, творить — это именно то, что нужно человеку социализма.
В своих выступлениях, статьях, приказах Н. И. Подвойский призывал, убеждал, требовал превратить в спортивные площадки и использовать для занятий каждый пустырь, каждый захламленный участок двора. Он ежедневно бывал на территориальных участках Всевобуча в столице. Довольно часто инструктора Всевобуча, секретари комсомольских организаций начинали увлеченно рассказывать ему, где и что они собираются сделать, а Николай Ильич, щурясь в улыбке, мягко обрывал их: