В начале следующего года один из родственников сэра Николаев сделал сумасбродную попытку ограбить казначейство, чтобы добыть деньги для готовившегося тогда нового восстания протестантов. Николае, не связанный, кажется, с этой попыткой, должен был внести огромную сумму в 2 тыс. ф. ст. как залог своей верности правительству. Почва начала гореть под ногами Николае Трокмортон махнул рукой на залог и в конце июня 1556 г. уехал во Францию. Однако, в отличие от других эмигрантов-протестантов, бежавших от преследований правительства католической королевы, Николае Трокмортон сразу же во Франции явился к британскому послу доктору Уоттону, клятвенно заверил его, что не имеет ничего общего с мятежниками, и попросил переслать его оправдательные письма Марии Тюдор и влиятельным членам Тайного совета. Это было очень важно Трокмортону, надо было спасти от конфискации свои имения (часть из них все же пришлось продать, чтобы покрыть расходы во Франции). Не ясно, действительно ли Трокмортон избегал других эмигрантов, во всяком случае, он часто бывал у посла, снабжая его многими полезными сведениями. Англия как союзница Испании готовилась развернуть военные действия против Франции. Поэтому для английского правительства оказалась крайне важной информация, собранная Трокмор-тоном, о военных планах французов, включая подготовку к высадке десанта в Англии. Сведения, добытые Трокмортоном, свидетельствуют, что он к этому времени уже обладал навыками опытного крупного разведчика. Он получил прощение за свое бегство, а после участия на стороне испанцев в битве при Сен-Кентене в августе 1557 г., закончившейся разгромом французских войск, был полностью амнистирован (этому, по-видимому, помог его младший брат - ревностный католик, который стал приближенным Марии Тюдор).
Таким образом Трокмортон прожил годы правления Марии Тюдор, а уже на другой день после ее смерти получил важные поручения от новой королевы. Он надеялся занять высокий пост в правительстве - стать вторым человеком после Уильяма Сесила. Но его непрошеные советы и рекомендации не были приняты королевой. От этих дней у Трокмортона осталось острое чувство зависти к Сесилу, которое побуждало его принимать сторону противников главного министра, конечно, противников из среды елизаветинской администрации, а не врагов самой королевы. Впрочем, Сесил, закрыв Трокмортону путь к участию в правительстве, охотно согласился предоставить беспокойному сэру Николасу дипломатический пост. В мае 1559 г. Трокмортон был назначен постоянным послом в Париж (в отличие от чрезвычайных послов, направлявшихся с каким-то особо важным специальным поручением).
Трокмортон был сторонником энергичных мер против всех врагов Елизаветы. Эту линию отстаивал фаворит королевы Роберт Дадли, граф Лейстер, тогда как Сесил считал, что выгоднее придерживаться более осторожной и гибкой политики. Однако при всем том Трокмортон старался все же сохранять верность Сесилу как главе британской секретной службы.
Сэр Николае прибыл в Париж, когда в 1559 г. был заключен Като-Камбрезийский мир, который положил конец военному конфликту между Испанией и Францией, длившемуся всю первую половину века. Вдобавок испанский король Филипп II и французский король Генрих II "частным образом" договорились уничтожить еретиков в своих странах. Возникла возможность коалиции двух наиболее мощных католических держав против Англии возможность, которая в течение многих десятилетий считалась в Лондоне наибольшей внешнеполитической опасностью. Обе эти страны обладали средствами давления на Англию - Филипп II владел Нидерландами, торговля с которыми имела чрезвычайно большое значение для британских купцов. Нидерландские гавани были самым удобным местом, откуда армия неприятеля могла достичь английских берегов. Франция имела серьезные позиции в Шотландии. Регентшей Шотландии была вдова короля Якова V Мария Гиз - представительница аристократического рода, который имел большое влияние на французскую политику. А дочь Марии Гиз - Мария Стюарт, которая с детских лет жила в Париже и была обвенчана с французским дофином, являлась королевой Шотландии. Более того, как родственница Тюдоров, Мария Стюарт имела права и на английский престол, которые могли превратить ее в соперницу Елизаветы, поддерживаемую английскими католиками. Притязания Марии Стюарт встречали полное одобрение Гизов.
Война против Франции, начатая еще при Марии Тюдор без всякой подготовки, была неудачной. В 1558 г. англичане лишились своего последнего опорного пункта на континенте - французского города Кале, который был ими завоеван в XIV в. Трокмортон получил инструкцию выразить согласие с Като-Камбрезийским договором. Вместе с тем посол должен был действовать, исходя из того, что главными непосредственными задачами английской политики были выдворение французов из Шотландии и возвращение Кале. Трокмортону были даны поручения, явно не укладывавшиеся в его дипломатические функции, точно разузнать, что собираются предпринимать Гизы в отношении Шотландии (причем чрезмерная любознательность английского посла не должна быть замечена). Трокмортон должен был также устроить побег из Франции шотландского графа Эррана, имевшего права на шотландский престол. Однако Трокмортон свои задачи понимал еще шире. Он один из первых почувствовал, какие выгоды может извлечь для себя протестантская Англия, поддерживая протестантские силы в различных странах Европы, и прежде всего французских гугенотов. Помощь протестантам в надвигавшейся религиозной войне во Франции могла стать наилучшим способом достижения Лондоном внешнеполитических целей.
Едва Трокмортон обосновался в Париже, как Генрих II в начале июля 1559 г. был смертельно ранен, участвуя в рыцарском турнире. Через несколько дней король скончался, на престол вступил его сын Франциск II, муж Марии Стюарт, а Гизы установили полный контроль над правительством и подготовили посылку значительных французских подкреплений в Шотландию. Тревожные депеши Трокмортона Сесил использовал, чтобы сломить сопротивление Елизаветы против плана английской вооруженной интервенции в Шотландию. Осенью 1559 г. Трокмортон был отозван, в марте следующего года начались военные действия. Превосходство англичан на море заставило Гизов согласиться на эвакуацию французских войск из Шотландии - таковы были условия Эдинбургского договора, добиться ратификации которого Марией Стюарт Елизавета поручила Трокмортону, снова отправившемуся для этой цели в Париж. К этому времени Трокмортон был уже заметной фигурой на европейской дипломатической сцене. Впрочем, его акции в глазах английской королевы были подорваны бестактными советами, которыми продолжал докучать ей сэр Николае. Положение мало менялось даже тогда, когда советы преподносились под видом донесений, в которые включались слухи, ходившие о Елизавете при французском дворе.
Другим активным разведчиком тех лет был Генри Киллигрю, посланный во Францию для связи с гугенотами. Сэр Генри в известном смысле являлся противоположностью Николасу Трокмортону. Снедаемый страстями, Трокмортон не раз шел собственными путями, которые вызывали неудовольствие королевы и ее министров. Киллигрю, напротив, был идеальным, почти безликим слугой тюдоровской монархии, всегда послушным, неколебимым в своем усердии, готовым без малейших угрызений совести на любые действия, включая убийство, если только оно соответствовало государственным интересам в том смысле, какой вкладывали в это понятие Елизавета и ее советники. Мария Стюарт оказала Киллигрю во Франции важные услуги, так же как и Трокмортону, который запомнил это и пытался совместить преданность Елизавете с поисками политики, которая не вредила бы и шотландской королеве. Иное дело - Киллигрю. Он сразу же с холодной ненавистью стал самым непримиримым ее врагом - ненавистью, целиком вызванной трезвым политическим расчетом. Однако во Франции и Трокмортон, и Киллигрю еще действовали в полном согласии для осуществления целей явной и тайной дипломатии елизаветинского правительства. Уже в июле 1559 г. Трокмортон многозначительно известил королеву, что Киллигрю сослужил ей "многими различными способами столь добрую и трудную службу, что заслуживает хорошей награды".
В Лондоне считали, что герцог Гиз, обладавший большим влиянием при французском дворе, постарается силой поддержать притязания своей племянницы Марии Стюарт. Вдобавок в Шотландии все еще находилось некоторое количество французских войск. Задачей английской секретной службы поэтому стало всяческое поощрение политической и религиозной оппозиции и в Шотландии, и во Франции. Трокмортон и Киллигрю вполне подходили для выполнения подчас весьма щекотливых поручений, связанных с такой политикой. В июле 1559 г. Киллигрю удалось устроить бегство из Франции графа Эррана, который был нужен английской разведке в Шотландии. Киллигрю действовал вместе с английскими разведчиками Томасом Рэндолфом и Ричардом Тремэйном.