Like Pheidippedes, most early distance runners were messengers. They were so important that even a god of Greek mythology, Hermes, was given the role of messenger. The need for messengers was mostly related to how bad the roads were in most parts of Europe. As any competitive person can imagine, races between messengers probably started with bragging by one or the other about their exploits. By the end of the 18th century the occupation of foot messenger had pretty much died out - but, foot races - especially in Britain went on.
The first races, in the 17th and 18th centuries, were usually sponsored by pubs. Like boxing, gambling, was the main draw for spectators. Also like boxing - the men who raced were mostly from the lower classes. However, by the mid-19th century schools as like Oxford and Cambridge were fielding cross-country teams - making it a "respectable" sport. However, there was a distinction between pro's who ran for money and amateurs who ran it for fun. This split is why the Olympics was only for amateurs at the beginning - they wanted the event to have a more "noble" atmosphere than could be found at most professional races. Given the doping issues that track has now - maybe they were on to something.
Most of this historical information I took from Lore of Running, by Tim Noakes, MD. At over 700 pages, it is the text book of running - as in, you wouldn't want to read the whole thing unless you were going to be tested on it.