[Retric]

Medieval people where aware that you could send messages faster than a horse.

Flag signaling between boats is very old and eventually turned into a messaging system that could go 191 km in 5 minutes. Smoke signals where perhaps the oldest form of long distance communication, and was used across the full 7,300 kilometres Great Wall of China. Though actual speeds are less clear.

For physical messages, attaching them to projectiles or birds was also used. A man on foot or a horse had other advantages.