The Milton Post Office is established on December 3, 1878. Walter D. Cotton is the first postmaster. The post office is located 18 miles south of Seattle within the future city limits of Federal Way. The post office went through several names: Milton, Buenna, Stones, and finally Redondo. This Milton should not be confused with a Milton located in Pierce County near Tacoma, nor with a Milton located on Duwamish Head in Seattle.
From March 10, 1879 to July 18, 1888, the post office did not operate. It reopened on July 18, 1888. Lorenzo D. Hurlbut was the postmaster.
Milton was located one mile from Stone's Landing on Puget Sound. In 1889, the town had a population of about 150 people, a Congregational church, and two sawmills. Milton also had orchards and produced fruit. There were 60 school children in the surrounding district. A daily steamer to Tacoma cost 75 cents.
In 1890, the Milton Post Office closed and the name of the town changed to Buenna (on September 19). The new Buenna Post Office opened right next to Puget Sound, on Poverty Bay, where most of the commercial activity had always taken place. Joseph P. Bucey was the postmaster. Buenna is located 19 miles south of Seattle 1.25 miles southwest of Redondo near Puget Sound.
On February 12, 1899, the name changed to Stones. Joseph P. Bucey was still the postmaster at the time of this name change. On October 8, 1904, the named changed to Redondo.
Operation of the Redondo Post Office was transferred to the Auburn Post Office on September 14, 1963.
At each name change the post office had a different location: Milton, about two miles west of the 1960 location of the Redondo Post Office; Buenna about 1.25 miles southwest; and Stones at Stones Landing along Puget Sound.