Lighter wrote:

"Taylor showed that an actual song somewhat resembling "Sir Aldingar" existed in the twelfth century. Of course, we don't have the lyrics or the tune, and there is no evidence of continuity across several centuries."

Those caveats are wise: the 12th century version of 'Sir Aldingar' (postulated by Christopherson in 'The Ballad of Sir Aldingar, its Origins and Analogues') seems to be completely conjectural, although historical / mythical prose accounts on a similar theme do go back to that period. The oldest Scandinavian ballad analogue (which tells a story different in several respects) is from the 16th century, while the Percy Folio, from which the English ballad (Child 59A) originates, is from the 17th century.

The stories of ballads like 'Hind Horn' and 'Sir Eglamore' (= 'Old Bangum') occur in medieval metrical romances, but how they were made into ballad form is unknown. The hero's disguise as a beggar in 'Hind Horn' also echoes the Odyssey. As Suibhne says, several ballad themes are ancient, even if the ballads themselves are not demonstrably so.

Other authors have agreed with those above who have questioned 'Judas' as a true ballad (though I don't doubt Paul D has put together a good version). I tend to agree that Child 1 ('Riddles') is the oldest known of the true ballads, although as Lighter points out, the 1445 copy 'Inter Diabolus et Virgo' doesn't have the narrative framework surrounding the riddles, which seems to have been grafted on later.

There's a good online summary of early Child ballads here from Greg Lindahl, early music enthusiast and founder of the 'Society for Creative Anachronism'.

I'm surprised that Steve Gardham hasn't visited this thread yet!