When I say "song", I mean the combination of tune and words; and yes I'm probably thinking Ashkenazically here. It seems like any European old-timer I've met knows the "good old fashioned" tune for Psalm 23 (Mizmor L'Dovid, Hashem ro'i lo echsar). How old is that? More generally, what are the oldest songs still popular today?
I have heard from my uncle, who has been very active in the Jewish Music industry, that when he played the tune Ashkenazim use for singing the seder (order) of the Seder Night (Kadesh, Urchatz, etc.) for his music professor, the professor exclaimed that the tune was at least 1000 years old.
Then I sang the tune for some sefardic friends who exclaimed that they use the same tune (albeit with some Middle Eastern twists). They sang it and lo and behold it is the same tune Ashkenazim use! Who knows how old that tune is?!
Cantor Sherwood Goffin has an excellent article on these ancient "MiSinai" melodies. One example is the tune for Borchu in Maariv during the Yamim Noraim, which is at least 1100 years old!
The Previous Lubavitcher Rebbe said in a sicha that the Skarbova niggunim ([literally means "old", these niggunim are traditionally sung on Rosh Hashana and Yom Kippur) were written by the Maharal. In his time there were troubles for Jews, so the Maharal asked Shmayim for davening melodies that would arouse heavenly mercy. Based on those, he established the skarbova niggunim.
The Tzemach Tzedek (third Lubavitcher Rebbe) said that skarbove niggunim were sung by the Levites in the Beis Hamikdash.
This is why these melodies are generally considered "exclusive", and Rabbonim were very Makpid not to change these tunes.
It's much harder to get older than the Levites, yet here is a niggun that has both its melody and words atrributed to the AriZal (1500s).
I have heard (from a rabbi then in Rhode Island, who apparently had researched this, but I forget his name and, indeed, what city he was in) that many (most? all? I forget) of our (Ashkenazi) nuschaos (tunes used for prayer, not the songs but the, if you will, chants used throughout the prayer to distinguish, e.g., holiday from weekday prayers) are as old as the Maharil, which would be in line with Shalom's comment above that "a handful of tunes used in the davening -- e.g. half-kaddish before Shabbos musaf -- can be tracked clearly to the 1400s".
See here for an article about sheet music found on a 370 year haggadah for a couple of Pesach songs. The tune for Adir Hu is very similar to one commonly used today.
I'm not sure if it's still of interest, but regarding a tune for Mizmor L'Dovid (Psalm 23), the popular one typically sung during Seudat Shlishit on Shabbat was composed by Rabbi Ben Zion Shenker.
Here's a link to the song as sung by Cantor Leon Lissek: Mizmor L'David-Psalm 23-A Song of David by Ben Zion Shenker (YouTube).
NPR did a story about him in 2013 titled "The Greatest Living Figure Of Chasidic Music".
People like him are the exact reason why I put so much time into researching the authors and composers of songs when preparing my YouTube videos. If the songs are still under copyright, as his are, it's very important to know.
I hope that's helpful.
Maoz Tzur and it's famous tune have been going hand in hand since the 1450's. According to wiki the tune is an adaptation of an old nonjewish song, but I don't think that would disqualify it from being included here. The content of the song was started to be written in the thirteenth century, during the crusades.
What the article doesn't address is that this song and it's tune are commonly sung amongst Sefardim also.