Когда Фирюбин приехал в Прагу, страна медленно приходила в себя после тяжелых сталинских лет. Николаю Павловичу было поручено наладить и укрепить дружеские связи, демонстрируя и доказывая равноправность отношений между двумя странами.

Работа в государствах, которые после войны вошли в орбиту советского влияния, стала для Москвы наиважнейшей. Еще при Сталине приняли решение прекратить разведывательную деятельность в странах народной демократии. Зарубежный аппарат внешней разведки в Чехословакии получил команду отказаться от сотрудничества с «негласными помощниками». Послу поручили довести до сведения руководителей страны, что советская разведка в их государстве больше не работает: «Такое решение принято, исходя из единства политических целей и задач, а также взаимного доверия между СССР и странами народной демократии».

Советникам при органах государственной безопасности разрешалось давать «практические советы только в устной форме». Запрещалось вмешиваться в решение кадровых вопросов, допрашивать арестованных и участвовать в оперативной разработке высших руководителей страны. Вербовать агентуру запрещалось. То есть нельзя было оформлять отношения, брать подписку о готовности сотрудничать, заводить дело и присваивать псевдоним. Но в этом и не было нужды. Чешские и словацкие чиновники охотно шли на контакт с советскими представителями, были с ними необыкновенно откровенны и рассказывали все, что знали. Добрые отношения с влиятельными советскими чиновниками были залогом успешной карьеры.

Фирюбин старался вести дела по-новому. Но начатые при Сталине интриги давали о себе знать. Еще в 1954 году продолжалась история с Густавом Гусаком, которого после ввода советских войск в Чехословакию для подавления Пражской весны сделают хозяином страны, а тогда просто гнобили.

Густав Гусак активно участвовал в подготовке словацкого национального восстания в августе 1944 года. После войны предложил присоединить Словакию к Советскому Союзу, но Прага его не поддержала. Более того, Гусака зачислили в «буржуазные словацкие националисты». Им заинтересовались советники из Министерства госбезопасности СССР. Разумеется, сыграли свою роль и внутренние склоки и противоречия в руководстве республики. Гусак своими манерами и образованностью отличался от малограмотных аппаратчиков. Они презрительно именовали его «барином». Советские чекисты представили фальсифицированные материалы, из которых следовало, что Гусак готовил покушение на вождя коммунистов Клемента Готвальда. По спискам, составленным с помощью советских чекистов, в Словакии арестовали несколько десятков человек, в том числе Гусака. В апреле 1954 года он был приговорен к пожизненному заключению на процессе по делу «словацких буржуазных националистов». Пересмотр кампании репрессий в Чехословакии начался значительно позже, чем в Советском Союзе. Только в мае 1960 года Гусака амнистировали и освободили.

Из Чехословакии Николая Фирюбина в сентябре 1955 года перевели послом в Белград. Екатерина Алексеевна переживала — разлука продолжалась. Для Фирюбина новое назначение было свидетельством признания его успешной работы. В силу особо сложных отношений с югославским лидером Иосипом Броз Тито это был крайне важный пост.

Сталин поссорился с руководителем социалистической Югославии. Тито не только проявил своеволие, но и не изъявил желания каяться и просить прощения. Тито храбро сражался во время Второй мировой и стал хозяином Югославии по праву победителя. Он был единственным коммунистическим руководителем в Восточной Европе, который получил власть не из рук Сталина.

Все остальные прекрасно понимали, кому они обязаны своим положением.