Комплектование штатов шло не только за счет ранее упраздненных контрольных органов. Использовались многие источники — подходящие специалисты запрашивались из аппаратов других наркоматов и с производства, отбирались из числа выпускников вузов, вызывались в Москву с мест. Некоторое число работников ему разрешили взять из военного ведомства: к концу февраля 1941 года только в центральном аппарате НКГК трудились около 130 военнослужащих. Кроме того, он добился решения ЦК партии, обязывавшее руководство наркоматов обороны и ВМФ выделить в его распоряжение необходимые кадры для назначения контролерами в военные округа, армии, дивизии и на крупные склады.
Мехлис организовал работу по срочному формированию наркоматов госконтроля союзных республик и подбору кандидатур наркомов. Политбюро ЦК ВКП(б) оперативно утвердило по его представлениям З. И. Али-Заде (Азербайджанская ССР), A.A. Бунятяна (Армянская ССР), А. Х. Бутко (Молдавская ССР), И. Ф. Волошина (Белорусская ССР), А. К. Койшигулова (Казахская ССР). Позднее в рабочем порядке были произведены назначения наркомов и в других союзных республиках.
Нарком госконтроля СССР проявлял необходимую взыскательность и соглашался с далеко не каждым предложением республиканских партийных органов. Так, кандидатура Койшигулова была принята им при условии, что наркому госконтроля Казахстана будет придан толковый, знающий заместитель. А кандидатуру К. Мукумбаева, начальника Бухарского областного отдела НКВД, предлагавшегося ЦК КП(б) Узбекистана на пост республиканского наркома, и вовсе отвел. «Считаю, что он по своей общей культуре и грамотности с работой наркома госконтроля не справится», — после личной беседы с кандидатом резюмировал Мехлис в письме Молотову.
Параллельно формировались и штаты наркоматов союзных республик. Вместе с аппаратом союзного наркомата в подчинении у Мехлиса оказалась целая армия контролеров — более 4,5 тыс. человек.
В решении кадровых вопросов наиболее сложным звеном оказался подбор руководителей среднего звена и рядовых сотрудников. Лев Захарович требовал от своих заместителей, от главных контролеров оценивать людей, прежде всего, по политическим качествам. Несмотря на то что к этому времени волна массовых репрессий спала, недавняя атмосфера всеобщей подозрительности, массового выявления фактов «вредительства» буквально во всех отраслях народного хозяйства, во всех сферах жизни сказывалась сильно. В результате многие кандидатуры отводились даже при наличии, казалось бы, веских аргументов в пользу назначения на должность.
Строго следя за политическим лицом подчиненных, нарком обращал много внимания и на их деловые качества, предупреждал контролеров против бездумного увлечения возможностью карать, требовал разбираться с выявленными нарушениями без торопливости, при участии проверяемых должностных лиц. С теми, кто эти требования не выдерживал, расставался. Так, в декабре 1940 года был снят с должности и уволен из НКГК главный контролер по Народному комиссариату торговли Г. Я. Удрас. Во время проверки состояния торговли и общественного питания на заводах оборонной промышленности, проводившейся по поручению ЦК ВКП(б), он проявил недобросовестность и необъективность.
Мехлис проявил ясное понимание того, что контролерские функции качественно сможет исполнять только квалифицированный работник. Учитывая недостаточно высокий образовательный уровень контролерского состава, а также то обстоятельство, что многие приходили на эту работу из других сфер деятельности, нарком неоднократно давал указания о дополнительной учебе подчиненных. Одним из своих первых приказов он утвердил порядок изучения работниками наркомата основ бухгалтерского учета, экономики и финансов. По прошествии нескольких месяцев было признано необходимым поднять уровень таких занятий. Для старших контролеров, контролеров и их помощников вводился техминимум с последующей сдачей зачетов по основам бухгалтерского учета, финансам, кредиту и их планированию, основам хозяйственного и уголовного права и другим дисциплинам.
Несмотря на значительные усилия, заполнение вакансий все время шло трудно. Не хватало руководителей (главных контролеров и их заместителей), недоставало наиболее массовой категории специалистов — контролеров, в течение длительного срока не удавалось укомплектовать группу ревизоров, состоявших непосредственно при наркоме для выполнения оперативных заданий. На 1 января 1942 года центральный аппарат был заполнен всего на 60 процентов (при том, что в армию с началом войны было призвано не так уже много — 141 человек), а укомплектованность контролерским составом оказалась еще ниже — от 40 до 60 процентов.