Mary expelled the English diplomat Thomas Randolph and Elizabeth ordered Melville's return to Scotland on 15 March 1566.
[4] When Mary was captured at the battle of Carberry, Melville took Elizabeth's letters to her at Lochleven Castle and brought her requests to the Confederate Lords and her supporters.
On the day that James VI of Scotland was crowned he wrote to Elizabeth that her ambassador Nicolas Throckmorton had helped defuse the situation and save Mary's life.
[5] Melville worked for Regent Moray, and arranged with Sir Valentine Browne, treasurer of Berwick, for loans of money secured with pledges of Mary's jewels.
At the end of the "lang siege", Grange, Melville, and the Laird of Pittadro climbed down the castle walls on a rope to negotiate their surrender with William Drury.
[12] On 19 October 1573 Melville was questioned about negotiations for the marriage of Mary Queen of Scots to John of Austria, her escape from Lochleven Castle, her good and jewels, her proposed marriage to Thomas Howard, 4th Duke of Norfolk, the siege of Edinburgh Castle and those who supplied it with silver or gave loans secured against pledges of Mary's jewels.
Margaret Winstar, a Danish servant of Anne of Denmark, helped her lover, the rebel John Wemyss of Logie escape from the palace.
James VI was angry and held a council, and sent the Earl of Morton and Melville to the queen to demand she sent Winstar back to Denmark.
His mission was to collect a subsidy or annuity of £4,000 which Elizabeth gave to James VI, and ask for 34 elm trees for the king's garden.
James VI came to Holyrood Palace on 25 July 1595 from Stirling Castle, after receiving a letter from Melville assuring him the queen was ill, on the testimony of the Mistress of Ochiltree and other gentlewomen.