In 1897 F. Jay Haynes was a successful Saint Paul studio photographer, who also operated a lucrative mobile studio out of a railroad car, and who held a photographic concession lease for Yellowstone National Park. Still, Haynes was one to look for or make opportunity. From 1898, when he commenced tourist transportation service to Yellowstone National Park through the west entrance until the company's forced dissolution in the concession reorganizations of 1916, Haynes and various partners were associated with two of the most financially successful staging operations in Yellowstone's history. The short-lived Yellowstone-Western Stage Company operated in only the three tourist season between 1914 and 1916 and succeeded the Monida and Yellowstone Stage Company which operated through the park from 1898 to the end of the 1913 season.

The name for Haynes first Company came from its terminal stops at the Oregon Short Line Railroad station at Monida, Montana, on the Idaho border, and from Yellowstone (later West Yellowstone), Montana, on the Park's extreme west border. Tourists were picked up at Monida and spent two days travelling before reaching the hotel at Norris Basin. An overnight stop in Centennial Valley, Shamboe's Ranch, hosted tourists the first night and meals were served at two other lunch stations: ___ and Dwelle's (west of present West Yellowstone). The road passed straight east from Monida into the Centennial Valley, crossed the Divide at Red Rock Pass and the Henry's Fork river, recrossed the Divide at Targhee Pass, and followed the Madison River to Norris Geyser Basin. Though he had been associated with the Northern Pacific Railroad as their official photographer since 1877, Haynes' stage line competed directly with the Yellowstone Park Transportation Company which was backed by the railroad. Haynes separated himself from the Northern Pacific in 1904. The trip was substantially shortened in 1907 when F. Jay Haynes was able to convince the Oregon Short Line Railroad (a Union Pacific affiliate) to build a spur from Saint Anthony, Idaho, to the western Park boundary solely for tourist business. After the line was completed in 1908, the two-day stage drive from Monida to the Park was eliminated. Business increased to a scale that by 1910 the Monida and Yellowstone Stage Company, the "Red Coach Line," was the single largest transportation company in the Park, a position it never relinquished.

In January, 1912, former partner and General Manager W.W. Humphrey instituted a suit over Monida and Yellowstone Stage Company stock ownership. The case was decided in favor of Haynes in 1913 but with the backing and probably at the instigation of former employer Huntley Child, owner/operator of the rival Yellowstone Park Transportation Company, Humphrey fought to have the Monida and Yellowstone Stage Company 's Park concession cancelled over ticket pricing practices. Haynes fought hard to retain his contract but lost it to forfeit in October, 1913. With the lease open to bid, F. Jay Haynes organized again under the name "Yellowstone-Western Stage Company" and was awarded lease. The Yellowstone-Western Stage Company bought out the plant of the Monida and Yellowstone Stage Company and Haynes was able to secure a new concession, and the lease left him in a superior bargaining position. From 1914 through 1916 the Yellowstone-Western Stage Company flourished. As a result of the opening of the Park to automobiles in 1915 Haynes enlisted the cooperation of the other companies conducting tourists through the Park in establishing Yellowstone's first motorized transport service, the Cody-Sylvan Pass Motor Company. The Cody-Sylvan Pass Motor Company carried passengers only for a single season between Cody, Wyoming, and the Lake Hotel area in the Park.

In October, 1916, Assistant Secretary of the Interior Steven Mather, a proponent of regulated monopoly, decided to completely reorganize business in Yellowstone. The National Park Service was created to superintend the nation's national parks and monuments, and in a series of meetings through November and December Mather mandated the consolidation of Yellowstone's various competitive interests into larger organizations that controlled a single business. Tourist auto camps were given to the Yellowstone Park Camping Company, hotels to the Yellowstone Park Hotel Company, photography and pictorial souvenirs to Jack E. Haynes, general stores to Hamilton, and transportation to the Yellowstone Park Transportation Company. The Cody-Sylvan Pass Motor Company was dissolved but the transportation business was directed to change from horse-drawn to automotive. Stock interests in companies were bought out and traded, and one specific requirement in the new structure was that F. Jay Haynes retire from business in the Park altogether. In 1917 Haynes retired from active business.

Haynes presided over the dissolution of the Yellowstone-Western Stage Company as assets were sold in 1917. Storage facilities for residual property was maintained in the company's name as late as 1921. Upon F. Jay Haynes' death in 1921 steps were taken to permanently close the books. Both companies were officially dissolved in 1922.