I've decided to put my comment as an answer, since it might get more to the point of the original question.
In the mid-to-late 1800s, tales of cowboys both famous and infamous were filtering into the eastern US, and piquing interest. The idea that the west was still wild, as opposed to New York City, for example, was fairly romantic and exciting. At the time, newspapers still told of Indian massacres (both of and by settlers) (example: New York Herald 1873). Publishers decided to take advantage of the interest, and began publishing inexpensive volumes that usually added sensationalism to fact-based accounts of actual events and people (as well as fully-fictional tales).
These became 'hugely successful.'
The Western as a specialized genre got its start in the "penny
dreadfuls" and later the "dime novels". Published in June 1860,
Malaeska; the Indian Wife of the White Hunter is considered the first
dime novel. These cheaply made books were hugely successful and
capitalized on the many stories that were being told about the
mountain men, outlaws, settlers, and lawmen who were taming the
western frontier. Many of these novels were fictionalized stories
based on actual people, such as Billy the Kid, Buffalo Bill, Wyatt
Earp (who was still alive at the time), Wild Bill Hickok, and Jesse
While other genres of these books were also in demand, particularly the detective story, the Westerns were still one of the most popular, even across the turn of the century. Dime novels gradually evolved into pulp fiction at around the same time as 'literary' western novels began being published.
Then, in 1902, the first Western movie was released (which was, in fact, one of the first narrative movies, period): The Great Train Robbery
So, to sum up, Westerns as a genre were extremely popular from the beginning, even as the events they portrayed were actually still happening. In fact, the very fact such events WERE currently happening in another part of the country was most likely the reason westerns (and cowboy culture) were so popular.