There's a popular tune used for kidush on the nights of the shalosh r'galim. (It's available on YouTube (but ignore the "shehechiyanu" part of that recording).)
Cantor Goffin refers to it as "Traditional / Corollary MiSinai", and therefore in his opinion, immutable. Not as iron-clad as something recorded by Maharil, "father of Ashkenazic custom", though.
So I think that means we have no record of it from the 1400s, making it likely newer than that. Afraid I don't know when, though.
Note that Cantor Goffin's halachic source is a statement of Ramah to respect communal practice, including traditional tunes. If I understand correctly, he argues that Ashkenazic Jews are bound by the traditional communal practices of their Eastern European ancestors. (However ... a responsum of Rabbi Moshe Feinstein allowing an Eastern European immigrant to change his garb from that of a traditional Eastern European Jew to that of an American Orthodox Jew -- i.e. a two-piece suit or the like -- argues that "communal practices" only retain their halachic force during geographic transplantation if a specific community relocates en masse at a single point in time, which is not the case other than the Frankfurt community of Washington Heights, plus perhaps a few Hassidic communities. Though on the other hand ... it could also be argued that some liturgical tunes have now been accepted as the communal practice of American Ashkenazim.)
So if the Maharil-endorsed tunes are "extra-strength tradition", I'd call this one "regular-strength tradition." Still quite potent, though.