In October 1573 and April 1576 he went on special embassies to France. He was sent to Scotland in February 1578, but too late to prevent the fall of James Douglas, 4th Earl of Morton. After the imprisonment of Morton in 1580 he returned to Scotland to conduct negotiations on his behalf. At a convention of the estates, held on 20 February 1581, besides presenting a paper declaring the "Intention of the Queen's Majesty and her Offers to the King of Scotland', he, in a speech of two hours" duration, denounced Esme Stewart, created by the king Duke of Lennox, as an agent of Rome. If anything, however, his bold intervention only helped to seal Morton's fate. Having failed to thwart the purposes of Lennox by a public accusation, he now attempted, with Elizabeth's sanction, to concoct a plot for the seizure of him and the young king; but, the plot having been betrayed, he fled to Berwick, after he had narrowly escaped death from a shot fired into the room he occupied in the provost's house at Edinburgh. Randolph was sent on his last mission to Scotland in January 1586 with instructions for the negotiation of a treaty between the two kingdoms, to which he succeeded in obtaining the signature of James VI.