To enlarge a little on Bruce Olson's comment above on alternative titles and the references at his site, Claude M. Simpson (The British Broadside Ballad and Its Music, 1966, p.97), discussing broadsides naming as tune Flying Fame states:

"The Shepherd and the King, beginning 'An elder time there was of yore' (Wood 401, Pepys, Euing, Lord Crawford, Harvard, Douce, Roxburghe; reprinted in Roxburghe Ballads III, 211). licensed in 1578, but no surviving copy earlier than c. 1625; found in Pills to Purge Melancholy V, 289)."

The song appears with music in Pills as The King and the Shepherd, and Gillian the Shepherd's Wife, and her churlish Answer to the King. Two broadside editions can be seen at Bodleian Library Broadside Ballads:

[The shepherd and the king, and of Gillian the shepherds wife] Printed between 1663 and 1674 for F. Coles, T. Vere, and I. Wright, [London]. Douce Ballads 1(1b)

The shepherd and the king, and of Gillian the shepherds wife Printed between 1624 and 1680 for F. Coles, in the Old Baily [London]. Wood 401(1)

F. J. Child (The English and Scottish Popular Ballads, III, p. 165, points out correspondences of narrative and text between no.135, Robin Hood and the Shepherd, and the King Alfred text in Old Ballads (London, 1723-5).