The precursors were respectful body movements (kneeling, creeping) accompanying speech in certain contexts for centuries, used for example (but by far not only) when talking to a person of divine origin.
The earliest forms of honorific speech eventually replaced those body movements at the Emperor's court, under Chinese influence which favored talking while standing erect or while bowing. During the Heian Period (794-1185), honorific speech forms spread from the Emperor's court to every village, gaining new forms along with new social contexts in which it was used. The language gained tremendous complexity and sensitivity to tiny differences in social status in this way over the subsequent centuries.
That complexity was reduced following WW2 after the Emperors denied their divine origin. It was drastically simplified across the board, not just when talking to the Emperor.
You are looking at that modern, greatly simplified system.
Example source: Jana Šoucová: The Japanese honorific language: its past, present, and future. In: Asian and African Studies, 14, 2005. (This article summarizes from a European perspective, but it draws heavily on prior Japanese research on the topic. Obviously this topic is mostly studied in Japan and written about in Japanese. Many other languages have elaborate politeness levels as well, with many specific features in common with the situation in contemporary Japan, but with quite different histories behind their introduction, so I recommend to stick to Japan based or derived research for your question.)
For additional research, you could look up "keigo history".
The question was edited to ask about the origins of the "-masu" form specifically. Let's see what Iwanami kogo jiten has to say about it. (The name of this dictionary might sound like a dictionary of odd old words for reference by the modern reader of not-that-old literature, but it is actually a pretty comprehensive etymological dictionary, although it's been also characterized as opinionated or excentric). Note that I'm using derived sources and not the actual dictionary in the following. The "-masu" form has, per this dictionary, developed from a verb "mairasu", whose modern counterpart is 参, "mairu", with meanings revolving about humbly visiting a somehow sacred place. It seems to have been dialectally used as a "humble suffix" of any verb during the late Tokugawa period (19th century), spread widely around the time of the Meiji restoration, and its meaning subsequently shifted into the "polite" form as part of that process. That's a pretty big semantic twist because I'd imagine a "humble suffix" to be used primarily with the 1st grammatical person (although it could have been used with any grammatical person), whereas the modern "-masu" form certainly isn't. Also, only the post-WW2 simplification of keigo gave the "-masu" form its prominent place in the language (as seen from afar, contrasted to other languages).