Tosefos to Munachos 20b s.v. ונפסל says:
כל תענית שלא שקעה עליו חמה לא שמיה תענית ומנהג אבותינו תורה היא שהכל נוהגין עד צאת הכוכבים
Although the period of Tosefos extends past the Ramban, it starts earlier, and the discussion is about Rabbeinu Tam's opinion who was a century or so before. So that is a possible earlier source.
The underlying principle in both cases is found in the Talmud under the principle of פוק חזי מאי עמא דבר - see that entry in Wikipedia for further variations on that idea.
As far as I know, that is what there is with regards to the exact (or close to it) wording and concept, but the concept extends not only to observed custom establishing the Halacha where the exact source is lost, but to the power of the custom itself, for example the Yerushalmi Pesachim 4:5 discusses the custom to not work on Tisha B'Av was not formally instituted by the Rabbis - but it is still obligatory where it was practiced (according to Rabban Shimon Ben Gamliel anyway).
Similarly Avos D'Rabbi Nasan 45 discusses a reward of women in this world is that they keep Rosh Chodesh more than men - a custom. This is brought in a parenthetical in the standard prints of Rashi Megillah 22b s.v. ראשי חדשים.