It's going to be a bit hard to pin this one down. The first manuscript ever found that contained an anywhere near understandable system for writing music came from sometime in the mid-eleventh century. Lots of chants and liturgical music were extant, of course. The trouvères and troubadours were roaming all over Europe about that time. Fascinating history, really—all tied up with monasteries, Latin scholars, Roman poetry, horny young monks, and Viking raids. Many scholars maintain that some of the older traditional ballads and secular songs were put together by wandering troubadours and minstrels, but most of the ones that survived did so through oral transmission. When you can find many of the older folk ballads in England, France, Germany, and Scandinavia that tell the same stories and have the same verse structure, it tends to support the troubadour / minstrel authorship theory.

The Greeks and the Romans had music, of course (instruments survived, but no written music as far as I've ever heard) and lots and lots of poetry. It's pretty certain that much if not all poetry was intoned, chanted, or sung, usually to the accompaniment of a lyre or similar instrument. I've heard that many Greek scholars and music historians maintain that portions of Homer's Iliad and Odyssey and other epic poetry were recited or chanted to the accompaniment of a lyre or harp.

I think the oldest European song was probably sung by some anonymous Neanderthal.

Don Firth