Kuznetsov was born into a peasant family of Russian ethnicity in the Yekaterinburgsky Uyezd of the Perm Governorate of the Russian Empire (present-day Sverdlovsk Oblast, Russia). He studied forestry in a technical school and, after discovering his linguistic talents, learned the German, Esperanto, Polish, Ukrainian and Mordvinic languages (particularly Erzya language). In 1926, at age 15, Kuznetsov enrolled at Tyumen Agricultural College but did not finish and was forced to return home because of the death of his father. During that time Kuznetsov joined the ranks of the Komsomol. At home he enrolled in the local forestry college but in 1929 Kuznetsov was accused of having counter-revolutionary origins and excluded from Komsomol and the college. After moving in 1930 to Kudymkar (Komi-Permyak Autonomous Okrug) Kuznetsov was recruited by the local department of the OGPU. In 1932 he enrolled into Sverdlovsk Industrial Institute and continued to study German and other foreign languages.