The area around the Sultan and Skykomish rivers was occupied by the Skykomish, a branch of the Snohomish people, prior to the arrival of American settlers. The Skykomish had a permanent village at the confluence named , along with a nearby fishery named . Following the discovery of a rich gold vein along the Sultan River, the land around the confluence was claimed for a homestead by John Nailor and his wife in 1880. Among the first arrivals to the area were Chinese prospectors, who later settled the land but were evicted in 1885. Nailor built a small store and hotel to serve miners and loggers, eventually serving as the first postmaster after the settlement received a post office in 1885. The town and river were named "Sultan", an anglicization of (also known as Tseul-dan), then chief of the Skykomish tribe.