The Queen valued Nicholas as a trustworthy messenger, where a matter needed discreet handling, and the bearer of it was likely to be in danger. In 1559-60 the Bishop of Aquila wrote to the King of Spain: 'The Queen has just sent to France an Englishman called Tremaine, a great heretic, who is to disembark in Brittany. I understand that he goes backwards and forwards with messages to the heretics in that country.' On one journey he was arrested when carrying letters in cipher, and Throckmorton, the English Ambassador in Paris, wrote to the Due de Guise, asking for his release. Nicholas was a special favourite of the Queen, but as he loved a camp better than a court, she gave him leave 'to enter into the service of the King of Navarre, by which means he will be better able to serve her.' The King of Navarre, however, did not greatly appreciate Tremayne, and a short time afterwards Throckmorton writes: 'The bearer, Mr Tremayne, came out of England with intent to see the wars in Almain, or elsewhere, thereby to be better able to serve the Queen. He has been here a good while to hearken which way the flame will rise to his purpose; but now, finding all the Princes in Christendom inclined to sit still, returns home. Desires Cecil to do something for him to help him to live, as it will be right well bestowed. The Queen will have a good servant in him, and Cecil an honest gentleman at his command.' Andrew had entered the army, and in Scotland reaped fame from the brilliant cavalry charge which drove the French back into Leith. Lord Grey wrote in 1560-61 that he had chosen Captain Tremayne to escort Lord James, 'because he is a gentleman of good behaviour, courtesy, and well trained, and also that he stands in the favour of the Lords of Scotland by reason of his valiant service at Leith.'