Слуцкий, который в то время был начальником ИНО, объяснял успехи Малого его личным обаянием и врожденным тактом. Это был крупный и красивый человек, за что его и прозвали «Der Lange» (крупный малый) коминтерновские подпольщики из Центральной Европы. Перебежчик Александр Орлов, имевший обыкновение очень резко отзываться по поводу большинства из своих бывших коллег по НКВД, вспоминал с приязнью, что у Малого было «сильное мужественное лицо и при этом открытые, почти детские, голубые глаза». Несмотря на свой внушительный вид и страстную приверженность идеалам Коминтерна, он вызывал во многих агентах ощущение внутренней уязвимости, что только усиливало их привязанность к нему. У Малого было мало общего с теми грубыми аппаратчиками, которые завладели НКВД в годы «Великого террора». По национальности он был венгр и еще до Первой мировой войны был посвящен в сан католического священника. Во время войны он стал капелланом австро-венгерской армии и был захвачен в плен русскими в Карпатах. Впоследствии в разговоре с одним из агентов он вспоминал:

«Я видел все ужасы, видел, как умирают в окопах молодые люди с отмороженными конечностями. Меня переводили из лагеря (для военнопленных) в лагерь, и я голодал наравне со всеми остальными пленными. Нас заедали вши, многие умирали от тифа. Я потерял веру в Бога, и когда вспыхнула революция, я примкнул к большевикам. Я порвал со своим прошлым. Я не венгр, не священник, не христианин, не даже чей-то сын. Я был лишь солдатом, „пропавшим без вести“. Я стал коммунистом, и остался им до сих пор.»

Вскоре после того, как Малый освободился из лагеря для военнопленных, его страстное желание защитить революцию от контрреволюции открыло ему двери в Чека. Его вера в Новый Иерусалим на земле, который будет свободен от эксплуатации человека человеком, перестала быть чисто религиозной и осталась с ним на всю жизнь. Но ее сильно поколебали ужасы Гражданской войны и коллективизации. Он вспоминал времена Гражданской войны так:

«Наши красные отряды „очищали“ деревни так же, как это делали белые. Все оставшееся население: старики, женщины, дети — расстреливалось из пулеметов за оказание помощи врагу. Я не мог слышать женских криков. Просто не мог.»

Во время «очистки» деревень Малый, по его словам, прятался и затыкал себе уши. Но он убеждал себя, что как только будет разгромлена контрреволюция, все ужасы Гражданской войны уйдут в прошлое. Однако они повторились в период коллективизации. «Я знал, что мы творим с крестьянством, — признавал Малый. — Очень многие были депортированы, очень многие убиты. Но я не уходил. Я надеялся, что у меня будет шанс искупить свою вину.» Он принял личное участие в деле человека, который был приговорен к смерти за полмешка картошки, который он украл, чтобы прокормить своих умирающих от голода детей. Малый убедил своего начальника рекомендовать изменить приговор на тюремное заключение. Кроме того, встретился с женой этого человека и заверил ее, что жизнь ее мужа спасена. «Это дело, — решил он, — и станет моим оправданием.»

«Но затем меня направили на двухнедельное задание. Как только вернулся, стал наводить справки по „моему делу“. Но не смог найти папки с делом. Побежал к начальнику. Он также не знал, что произошло, и мы вместе начали поиски папки. Наконец мы ее нашли. Поперек папки было начертано одно слово: „Расстрелян“.

На следующий же день Малый отправился в ИНО и попросил назначения за рубеж. И его первым заданием — очевидно, это случилось в конце 1932 года — была работа нелегалом ОГПУ в Германии. Несколько месяцев спустя после захвата власти нацистами он переехал в Вену. Его послание австрийскому агенту Хеде Массинг — а также, без сомнения, и Киму Филби — значительно отличалось от послания, распространенного Эрнстом Генри в Англии. Генри подчеркивал успех подпольной войны, которую вели фюнфергруппы немецких рабочих, а Малый утверждал, что борьбу с нацизмом надо вести из-за пределов германской границы: «Единственный способ бороться с фашизмом — это бороться извне. Мы не добились успеха внутри, поэтому надо действовать извне». В подпольной борьбе против международного фашизма Малый опирался на свой ранний большевистский идеализм, заражая агентов верой в окончательную победу Коммунистического Интернационала.

Филби получил первый опыт нелегальной работы на Коминтерн в Вене, действуя в качестве курьера между поставленными вне закона коммунистами Австрии и явками в Венгрии, Париже и Праге. В феврале 1934 года борьба между правыми и левыми в Австрии достигла, по словам Филби, «критической точки». Силы правого правительства Дольфуса и еще более радикальные боевики Хаймвера (их основатель князь Старемберг участвовал в неудавшемся гитлеровском путче в 1923 году) громили профсоюзные комитеты, левые газеты, организации социалистов, службы помощи бедным и даже отдельные домовладения. Артиллерийским огнем были уничтожены два крупных венских квартала, а девять лидеров-социалистов были повешены во дворе Верховного суда. И действия Филби в этой ситуации (а он занимался переправкой социалистов и коммунистов из страны), где он продемонстрировал смелость и смекалку, как не что иное убедили Малого в потенциале Филби как возможного агента НКВД. Корреспондент «Дейли Телеграф» Эрик Геде так описывает один из визитов Филби на его квартиру в Вене:

«Я открыл шкаф, чтобы что-нибудь себе выбрать. Когда Ким увидел там сразу несколько костюмов, он воскликнул: „Боже, у тебя их семь. Отдай их мне. Там шестеро друзей скрываются от виселицы в городской канализации.“ Мы запихнули костюмы в чемодан и, если верить Филби, они были использованы для переправки его друзей из их убежища через границу в Чехословакию.»

Филби впоследствии сказал своим детям, что, когда он еще был в Вене, «ему было дано задание по внедрению в британскую разведку, причем не имело значения, сколько времени ему на это понадобится». Это задание ему дал Малый, он же и отправил Филби обратно в Англию в мае 1934 года. Вслед за Филби из Вены в Лондон был послан и его контролер Арнольд Дейч, который в Вене работал на Малого как нелегал. Сегодня портрет Дейча висит рядом с портретом Малого в «комнате памяти» Первого главного управления. Подпись под ним оценивает его вклад в вербовку и управление кембриджскими агентами почти на том же уровне, что и вклад Малого.