According to tradition the inspiration for the design of St. Mark's came from the Stoke Poges Church near London. This ancient church, dating from 1080 A. D., was made famous as the site where Thomas Gray wrote ''Elegy in a Country Church Yard.'' The architectural style of St. Mark's is Old English with pointed arches, massive buttresses, plain finishing and a high-pitched shingle roof. The architect was Henry M. Congdon of New York City. Construction was begun in 1886. The stone work was done by Mr. William Toorey and the interior woodworking was done by Mr. George East. The red lava stone was quarried at Castle Rock, Colorado. Only the addition of the bell tower in 1925 has altered the profile of the 1886 construction. The interior of St. Mark's contains the original altar, wooden fixtures, pews and open beams placed in the building in 1888.
Many memorable events have occurred in St. Mark's history through the years. In November of 1903 Cheyenne was alive with the Tom Horn affair. Accused of killing young Willie Nickell, Horn was tried by jury, found guilty and sentenced to be hung. St. Mark's assistant rector, the Rev. Mr. Watson, tried converting Tom Horn the night before his execution and the rector, the Rev. Mr. Rafter, prayed on the hanging platform right up until the time of Horn's death. A special service was held at St. Mark's for Tom Horn after his death. The funeral of the wife and three small daughters of General John J. Pershing took place at St. Mark's on August 31, 1915. Mrs. Pershing, daughter of Wyoming's United States Senator Francis E. Warren, along with three of her four children had met their death in a fire at the Presidio army post in California. October 11, 1936, was another noteworthy date at St. Mark's. That day President Franklin D. Roosevelt and his wife Eleanor, entered the Church and quietly worshipped with the congregation. Roosevelt was in Cheyenne campaigning for his second term as President.