Yes. It is hard to ascertain how "old" a song is unless the words, at least, are written down. It is said that "Judas" dates from ca. 1300, and is the oldest recorded Child Ballad. That would make it "older" than Lord Randall.

Historically, liturgical pieces are the oldest recorded. Biblical psalms are surely very old, but no one knows what tunes, if any, they were sung to. It is safe to say that if there are songs, that is, poems or whatever with identifiable tunes, from Europe or from anywhere else that are older than 1100, we have no way of knowing what they are. That is, any identifiable song, from anywhere on Earth, not just "this particular tribe" is at the very least a thousand years more recent than the "Roman Conquest," (assuming you mean conquest of England).

It is not clear what "Holy Roman Conquest" you would have in mind. The "Holy Roman Empire" dates from aroung 1100-1200. There may be songs that old, although that is stretching things.