He made himself sufficiently prominent in Edward VI's time to find it necessary to flee to Paris on the accession of Mary.

But, like other rebels, he soon tired of exile, and his known value as a soldier rendered the negotiations for his pardon easy.

He soon found favour, and on 3 April 1555 Philip wrote to his treasurer, Dominico d'Orbea, ordering a pension of two hundred crowns to be paid to Randolph, who is described as colonel of infantry.

In 1563 he was made marshal of Havre (then called in England Newhaven), and aided the French Huguenots with two hundred men.

Elizabeth, on Randolph's return to England, made him Lieutenant-General of the Ordnance, and colonel of footmen in Ireland.