We refer to Moshe as "Moshe Rabbeinu". (It's interesting about the avos as well that we say, for example, Avraham Avinu; however, I'll keep that for a separate question.)
When was the first time (and where is it written) that Moshe was referred to as "Moshe Rabbeinu"?