The Roman Empire had the [cursus publicus][1], which maintained an infrastructure of horses and way stations.  The messenger himself was supplied by the one sending the message.  It was used for transporting messages, magistrates, and some heavy goods too.  Important messages typically travelled at roughly 50 miles per day.

  [1]: http://en.wikipedia.org/wiki/Cursus_publicus
  [2]: http://en.wikipedia.org/wiki/Royal_Road