 Milles was born in Kent about 1550, the son of Richard Milles of Ashford, by his first wife Joan, daughter of Thomas Glover of Ashford, and sister of Robert Glover.Educated at a free school, he entered public service about 1570, and during the next sixteen years was frequently employed in France, Flanders, and Scotland.He is said to have received a "chapeau winged" as an augmentation to his armorial bearings for his celerity on a mission to Henry IV of France.