In 1878, the Northern Pacific Railway decided to resume construction of its main line west to the Yellowstone River near Glendive, Montana. The company needed administrative offices and a passenger depot west of the Missouri River.
Under the direction of lead engineer Thomas Rosser, a former Confederate general associated with Fort Lincoln, the railway constructed a one-story, gable-roofed depot measuring 24 by 70 feet and surrounded by a 12-foot-wide platform. Three years later, the building became a freight warehouse when a new passenger depot was constructed. The original depot was sold and moved in 1912.
The New York architectural firm McKim, Mead & White designed the replacement. The firm also designed the original portion of the White House's West Wing and the New York City mansion of Northern Pacific president Henry Villard.
The 100-by-32-foot depot had a brick first floor and a wood-framed second floor with hipped dormers, topped by a bell-shaped cupola. Designed in the Queen Anne style, it was surrounded by an eight-foot-wide veranda supported by ornate iron pillars. Its 400-foot trackside platform could accommodate as many as eight passenger cars.
The ground floor, level with the platform, accommodated employees and travelers. It contained a 14-by-30-foot express room, 13-by-18-foot ticket office, and 14-by-30-foot baggage room. In keeping with the period's custom, a 29-by-39-foot waiting room for women and children was separated from the 29-by-30-foot men's waiting room so that women would not be exposed to the “rough language” considered common among men.
Construction began in June 1882 and was completed that November at a cost of $12,000 (about $400,000 in 2025 dollars).
The second floor housed railway management offices and a Western Union telegraph office staffed by as many as nine operators around the clock. A battery room held lead-acid wet-cell jars that supplied backup electrical power. East of the depot stood a plain one-story building containing the dining room and lunch counter, commonly called the “beanery.” The depot was described as the finest west of St. Paul.
A major fire in June 1920 began in defective electrical wiring, which likely ignited hydrogen released by batteries in the telegraph office. Furniture, tickets, and records were rescued from the first floor, but the second-floor telegraph, yardmaster, roadmaster, and trainmaster offices were destroyed. Temporary offices were established in spare cabooses parked east of the beanery.
Because the railroad was losing money, it rebuilt the second floor with a plain design, replacing the shingle siding with simple wooden siding. After receiving a new coat of paint, the depot remained in service until 1929, when the Colonial-style depot replaced it.