Василий Иванович Пудин родился 9 февраля 1901 года в деревне Клусово Ольговской волости Дмитровского уезда Московской губернии, в крестьянской семье. В 1913 году окончил трехклассную сельскую школу. Трудовую деятельность начал в 15 лет батраком. В 1916—1918 годах работал ломовым извозчиком в Дмитрове и в Москве, затем чернорабочим в московском авиапарке. В 1919 году вступил добровольцем в Красную Армию, участвовал в Гражданской войне, сражался с белыми на Кавказском фронте.

В 1921 году горком партии столицы Советской России направил Василия Пудина на работу в Московскую ЧК.

Из воспоминаний Василия Пудина:

«В то время партийные органы (а я вступил в члены РКП(б) в январе 1921 года) сами решали, на каком участке тот или иной коммунист может принести больше пользы Родине. Так я начал работать уполномоченным в Политическом бюро МЧК, которое разрабатывало контрреволюционные политические организации. В середине 1922 года меня перевели в контрразведывательный отдел ГПУ. Начальником КРО в то время являлся Артур Христианович Артузов.

Я стал работать в 6-м отделении КРО и с группой товарищей занимался разработкой савинковской организации “Народный союз защиты Родины и свободы”. Нам удалось внедриться в эту контрреволюционную организацию и заманить Савинкова на советскую территорию. В августе 1924 года он был арестован и предстал перед советским судом».

Принимая участие в оперативных мероприятиях контрразведывательного отдела, Василий Пудин проявил незаурядные храбрость и находчивость. Так, вместе со своим другом, известным впоследствии чекистом-разведчиком Григорием Сыроежкиным, он участвовал в задержании прибывшего нелегально в Москву эмиссара Бориса Савинкова полковника Сергея Павловского (операция «Синдикат-2»), выступая в роли «боевика» легендированной чекистами подпольной организации «Либеральные демократы». Захват происходил во время обеда. Василий, обладавший недюжинной физической силой, так «дружески обнял» Павловского, что тот не смог воспользоваться находившимися при нем оружием и гранатами.

В конце 1923 года Артур Артузов, являвшийся тогда руководителем контрразведывательного отдела ОГПУ, пригласил к себе в кабинет молодого чекиста. Он уже знал Василия Пудина как честного и смелого человека, обладавшего необыкновенно цепкой памятью, и поставил перед ним новое, уже разведывательное, задание. На этот раз ему предстояло под видом купца Василия Шилова направиться в Харбин для работы против белогвардейцев и их японских покровителей.