The story
From stage + coach, reflecting the fact that relay of horses was a typical aspect of the operation of the service.
Etymology from Wiktionary, CC BY-SA 4.0.
stage-coach
Today it means: A horse-drawn coach that runs routinely between two destinations to transport passengers and mail. Full definition →