Окончив шесть классов и не доучившись одного года до завершения полного семилетнего курса, в ноябре 1914 года 16‑летний Павел предоставил дирекции училища письменное согласие родителей на его исключение из училища для добровольного поступления в действующую армию. 21 ноября 1914 года он был зачислен в Уральский партизанский отряд (УПО), который вскоре был направлен на Северо-Западный фронт для проведения разведывательно-диверсионных операций на территории Литвы. Со слов Павла Семёновича известно, что 8 февраля 1915 года он был назначен помощником атамана УПО. Столь скорое и неожиданное выдвижение юного бойца произошло благодаря его смелым и решительным действиям в сложной фронтовой обстановке и прирождённым навыкам разведчика.
12 марта 1915 года недалеко от местечка Радвилишкис (Радзивилишки) Шавельского (Шяуляйского) уезда Ковенской губернии Российской империи произошли события, о которых Павел Семёнович скупо сообщает в своей автобиографии: «В одном из боев был тяжело ранен и взят в плен, где мне ампутировали правую ногу по среднюю часть бедра»… Через некоторое время едва начавшего передвигаться с помощью костылей Павла перевели из лазарета в лагерь для военнопленных, где на протяжении трёх лет изо дня в день ему приходилось преодолевать все мучения и тяготы немецкого плена.
После подписания в марте 1918 года Брест-Литовского мирного договора между Советской Россией и Центральными державами (Германией, Австро-Венгрией, Османской империей и Болгарией), обеспечившего России выход из Первой мировой войны, начался процесс возвращения пленных, в первую очередь инвалидов. Процесс этот, судя по всему, был нелёгким, поскольку по возвращении 19 июня 1918 года Павел Нестерок-Нестеренков находился в московском временном госпитале. Несмотря на отсутствие ноги, он записывается добровольцем в Красную армию, демонстрируя один из тех невероятных подвигов преодоления и самопожервования, которыми будет так богата советская история.
1 июля 1918 года Нестерок-Нестеренков был зачислен сотрудником отдела личного состава штаба Московского военного округа (МВО), а 15 июля он был направлен в распоряжение Басманного райвоенкомата (РВК) города Москвы, где в его обязанности входили подбор и формирование боеспособного полка численностью полторы тысячи штыков, а также организация боевой подготовки личного состава. По окончании ускоренного цикла обучения 34‑й рабочий полк Басманного района вошёл в состав 2‑й Московской рабочей дивизии, в дальнейшем переименованной в Особую интернациональную дивизию. Незаурядные деловые качества, проявленные Павлом при комплектовании полка, не остались незамеченными, и 15 августа он был назначен помощником, а 1 октября 1918 года – военным комендантом Басманного района Москвы. Вскоре он избирается депутатом райсовета, а в ноябре 1918 года становится членом РКП(б).
12 февраля 1919 года Нестерок-Нестеренков был освобождён от должности коменданта – уже Бауманского района Москвы – и распоряжением командующего войсками МВО направлен в распоряжение Реввоенсовета Украинского фронта, где 16 февраля он был назначен комиссаром бригады 2‑й Украинской Советской повстанческой дивизии, с 25 февраля по 8 июля был председателем Следственной комиссии с Чрезвычайными полномочиями той же дивизии, одновременно с 24 апреля по 22 мая – начальником Уманьского и Винницкого боевых участков, затем с 24 мая – полевым комендантом Винницкого района, с 6 июня – заместителем комиссара 2‑й Украинской Советской повстанческой дивизии.
10 июля 1919 года Павел Нестерок-Нестеренков становится начальником контрразведки, с 3 августа по 16 октября – начальником агентурной разведки 46‑й дивизии. Именно тогда, на Уманьщине, он и получает оперативный псевдоним «Уралец».
Создав количественное и качественное превосходство над силами Деникина на главном, орловско-курском, направлении, Красная армия перешла в октябре 1919 года в контрнаступление и начала теснить белых по всей линии фронта. В связи с этим 30 октября Павла Уральца отзывают с Украины в распоряжение РВСР и 13 ноября направляют в политуправление Восточного фронта. 16 декабря он прибывает в распоряжение члена РВС 5‑й армии тов. Смирнова. 20 декабря Томск был освобождён от остатков армии Колчака, и Павел Семёнович Уралец 29 декабря, в возрасте 22 лет, был назначен военным комиссаром города Томска и начальником томского гарнизона.
В это время в городе свирепствовали голод, разруха, тиф, уносившие тысячи жизней. На учёт было поставлено всё: хлеб, оружие, скот, транспорт, санитарно-медицинские кадры. Военкому приходилось действовать быстро и применять чрезвычайные меры. Вот один из его приказов того времени (газета «Знамя Революции», № 63, от 3 апреля 1920 г.): «Приказываю в воскресенье, 4 апреля, с 8 часов всем заведующим складами, кладовыми, хозяйственными цейхгаузами всех без исключения учреждений гор. Томска и его окрестностей, а также и отдельным частным лицам… быть с ключами у своих кладовых. Никакие объяснения не принимаются. Виновные в неисполнении сего приказа подлежат суду реввоентрибунала. Начальник гарнизона г. Томска, военный комиссар П. Уралец».
Но именно здесь в то тяжёлое время впервые проявилось его увлечение, невероятное для человека на костылях, – интерес к спорту и стремление организовать спортивную жизнь Томска. По инициативе военкома в мае 1920 года началось строительство стадиона на берегу реки Томь. Газета «Знамя Революции» от 5 мая 1920 года писала: «Ведутся подготовительные работы по благоустройству стадиона Лагерного сада, его расширение в сторону города. В саду будут проходить занятия всеми видами спорта. Разрабатывается проект постройки на этом месте большого стадиона». Открытие стадиона состоялось уже 13 июня, однако в отсутствие его организатора. 19 мая военком Томска Павел Уралец по его личному желанию был откомандирован в распоряжение Западно-Сибирского окружного военного комиссара для направления добровольцем на советско-польский фронт.
К этому времени обстановка на советско-польском фронте обострилась до предела. 25 апреля 1920 года польские войска атаковали позиции Красной армии по всей протяжённости украинской границы. 7 мая в оставленный частями РККА Киев вступила польская кавалерия. Вскоре полякам удалось создать на левом берегу Днепра плацдарм глубиной до 15 км. Для стабилизации положения южная часть Западного фронта РККА была преобразована в Юго-Западный фронт, командующим войсками которого был назначен Александр Ильич Егоров. Именно сюда в распоряжение политуправления Юго-Западного фронта 22 мая в должности военного комиссара 1‑й отдельной Красной добровольческой Западно-Сибирской стрелковой бригады прибыл Павел Семёнович Уралец. Однако командование фронта посчитало более целесообразным использовать опытного военкома для борьбы с внутренним врагом и 15 июля 1920 года откомандировало его в Одесский губвоенкомат, где велась активная борьба с многочисленными бандформированиями, действовавшими на территории Украины. Отличившись в этих боях, 18 марта 1921 года Павел Уралец становится чекистом – его переводят в распоряжение штаба войск ВЧК Украины, где он был назначен помощником командира 26‑й отдельной бригады войск ВЧК, а с 18 мая по 7 октября являлся помощником начальника Донецкой дивизии войск ВЧК. 5 декабря 1921 года Уральца направляют в Ташкент на должность заместителя начальника политсекретариата и военкома штаба войск ВЧК – ГПУ Туркестана.
16 ноября 1922 года Уралец был отозван в Москву в распоряжение ГПУ и 5 декабря назначен заместителем начальника политсекретариата и старшим инспектором войск ГПУ Московского округа (МО) и 14 декабря по совместительству – заместителем военкома штаба войск ГПУ МО. В его обязанности входило проведение политико-воспитательной и культурно-просветительской работы с личным составом. Вскоре он обратил внимание на то, с каким азартом красноармейцы участвуют в стихийно возникающих спортивных состязаниях. У него возникла идея создать структуру, которая обеспечила бы все необходимые условия для занятий спортом для всех желающих из числа подведомственных ГПУ служб.
В феврале 1923 года состоялось собрание инициативной группы по созданию первого в стране спортивного общества. В состав группы, помимо Павла Семёновича Уральца, вошли начальник политсекретариата войск ГПУ МО Леонид Владимирович Недоля-Гончаренко, начальник орготделения политсекретариата войск ГПУ МО Кирилл Иванович Кузьмин, начальник отдела штаба войск ГПУ МО Михаил Иванович Лаврентьев и старший инспектор штаба войск ГПУ МО Дмитрий Константинович Иванов.
Впоследствии Павел Семёнович Уралец так изложил свои предложения, вынесенные на суд группы товарищей: «Цели общества мыслились как утилитарные – подготовка к несению военной службы, так и общефизкультурные – оздоровление членов общества, интересное и полезное использование свободного времени красноармейцев, предоставление им возможности осуществлять естественную тягу к физическим состязаниям. Приобщение к физической культуре максимального количества людей путем наглядной пропаганды состязаний, пропаганды физической культуры и спорта через демобилизованных красноармейцев в местах их постоянного проживания, особенно в деревне. И, наконец, создание материальной базы для занятий спортом. Общество должно культивировать любые виды спорта, если появлялись желающие ими заниматься. Состязания и рекорды признавались наряду с общеоздоровительными упражнениями средствами достижения поставленных целей. Организация научного и медицинского контроля и ответственность общества за здоровье своих членов. Физкультура в том виде, как она проводилась (в то время), не соответствовала моим представлениям о спорте. Заботы политработника, да к тому же войск ГПУ, привели меня к мысли, что спорт нужен для службы, для физической разрядки, для использования свободного времени. Наконец, для удовольствия. Спорт в полном смысле слова, но под медицинским контролем. При этих условиях он служит пролетариату, его диктатуре, советскому обществу. Форма организации должна быть самостоятельной, противопоставленной обязательным воинским упражнениям. Иначе говоря, должно быть организовано спортивное общество».