Николай Павленко родился в 1912 году под Киевом в с. Новые Соколы в семье мельника, где кроме него было еще семеро детей. В 1928 году, как бы предчувствуя грозящую опасность (отцу грозило раскулачивание), изменив в своих документах возраст (прибавив 4 года) и социальное происхождение, Николай сбежал из дома. Через несколько месяцев его семью действительно раскулачили и сослали в Сибирь. Более других Павленко привлекала профессия строителя, и он поступил в Калининский инженерно-строительный институт. Однако проучился там только 2 года и ушел. И опять вовремя. Это был канун чисток в среде интеллигенции и охоты на троцкистов. Николай устроился на стройку и вскоре написал донос в НКВД на двух сотрудников, Афанасьева и Волкова, обвиняя их в троцкизме. Эти двое и так уже находились под подозрением. Но теперь местный отдел НКВД рекомендовал Павленко, как благонадежного человека, в Главное управление военного строительства, где, работая прорабом, он постигал не только свою непосредственную работу, но и науку приписок и хищений. А кроме того, он быстро научился громко рапортовать о перевыполнении плана, даже если этого и не было, развивать идеологическую работу и дружить с органами безопасности. Репрессии 1930-х годов обеспечили ему карьерный рост. К началу 1940-х годов Павленко дорос до начальника строительного участка и уже начал было присматриваться к должности аппарата главка. Но тут началась Великая Отечественная война, и 80 % кадров Главвоенстроя были мобилизованы.
Пребывание на фронте не сулило ничего хорошего новоиспеченному воентехнику 1-го ранга (ст. лейтенант) Николаю Павленко. Стрелковый корпус, к которому он был приписан, оказался на одном из передовых участков фронта и нес огромные потери, и у Николая появилось огромное желание быть от фронта как можно дальше. В сентябре 1941 года, выписав себе фальшивое командировочное удостоверение, из которого следовало, что воентехник 1-го ранга Павленко H. М. послан на поиски аэродромной части, он вместе со своим шофером Щегловым дезертировал и отправился в хорошо ему знакомый г. Калинин. По дороге к нему примкнули еще несколько дезертиров, которые признали воентехника Павленко своим командиром неофициального воинского подразделения, абсолютно не желавшего воевать.
В Калинине у Павленко нашлось немало друзей и знакомых. Так что избавление от верной смерти он и его окружение длительное время отмечали бурными застольями. Но к марту 1942 года деньги кончились. Пришлось брать в долг у знакомых. Но и эти деньги быстро испарились. Павленко с компанией перестали пускать в рестораны, потребовали расчета в гостинице. И тогда Николай растерялся. Выход нашелся неожиданно. Один из друзей-дезертиров, Лев Рудниченко, как-то во время гулянки за час вырезал с помощью подручных средств из резиновой подошвы гербовую печать, отличавшуюся высоким качеством. Павленко быстро сориентировался. Как-то на строительной площадке автодорожной станции он увидел огромное количество брошенной в панике во время эвакуации строительной техники. Тогда у него созрела мысль создать некую фиктивную организацию, которая не только дала бы освобождение от фронта, но и приносила бы доход. Обстановка 1942 года как нельзя лучше подходила для афер с армейскими документами. Советские войска то наступали, то отступали. Неразбериха была полная. Даже командиры дивизий зачастую не знали, где находится та или иная часть. На это и рассчитывал Павленко. По его просьбе Рудниченко вырезал печать и штампы «Участок военно-строительных работ Калининского фронта» (УВСР-5). В условиях неразберихи появлению ниоткуда УВСР-5 никто не удивился. В результате некоторых манипуляций Павленко удалось открыть на имя УВСР-5 счет в Калининском банке. Местная типография отпечатала для него 18 тыс. фирменных бланков. Фабрики и склады безропотно выдавали павленковским бойцам продовольствие и обмундирование по фальшивым аттестатам. Вскоре дезертиры щеголяли в новенькой офицерской форме, а Павленко произвел себя в военные инженеры 3-го ранга.
Удивительно, но местная комендатура, где была зарегистрирована новая часть, ничего не заподозрила. Ротозейство и беспечность тылового начальства надолго обеспечили «процветание дела» Павленко. Никто вроде и не замечал, что за типографские бланки он расплатился продуктами, а комплекты обмундирования были украдены для него несколькими работниками местной швейной фабрики.