Prior to its being named Mayville, the settlement along Route 19 between Condon and Fossil was called Clyde, after a local blacksmith, whose last name is unknown. The town had sprung up to serve freighters and stages headed south to gold mining camps and established ranches. The town had a hotel, a general store, a gristmill, and even a "blind pig" (speakeasy).

Will and Phoebe McConnell and Will's brother Allen came to the stage stop at Clyde in early 1883 and took up land claims. A post office was established the same year. Earlier, a piece of the larger Wasco County had been designated as Gilliam County. The townspeople were eager to have their own county seat, but first they needed to be established as a civic entity. Will McConnell offered to draw a plat map for them, which he submitted in May 1883. The farmers approved the plat map and decided informally to call their new town Mayville because it was "born" in May. (The county seat went to Condon.)

In 1892, the Mayville Ladies Aid Society was founded and, for the men, the Independent Order of Odd Fellows (IOOF). The women spearheaded the construction of a small church, which served the community from 1897 until it was razed in 1951. Allen McConnell built a mercantile and Grange Hall, and Laura McConnell was the town’s undertaker and midwife. Edmund and Phebe Stinchfield operated a farm and stockyard, and in 1895, Ed helped build the Oddfellows Hall (IOOF). The hamlet was the site of the first Gilliam County fair in 1907.

Mayville suffered when a fire destroyed the hotel and gristmill sometime between 1907 and 1915, snuffing out two important sources of income for the town. Mayville’s fortunes changed again when Route 19 was paved, enabling travelers to speed through the burg on their way elsewhere. The school closed in the mid-1950s, and the rural post office closed in the 1960s, leaving Mayville a ghost town. The IOOF Hall is still there, as are several other abandoned buildings. Five or six houses are still occupied.