In 1971, voters defeated a proposal to annex part of the area between Bellevue and Renton and between Lake Washington and Cougar Mountain to Bellevue. In the early 1980s, residents applied to the King County Boundary Review Board to incorporate, but the panel decided that the proposed city did not have the tax base to support municipal operations. In 1990, the Washington State Legislature amended the statute for county boundary review boards looking at cities with populations of more than 7,500. The boards could amend proposed boundaries, and recommend against incorporation, but the measures had to go to the voters.
In April 1991, residents of unincorporated areas of King County such as Newport Hills and Hazelwood, between Bellevue and Renton, began meeting to discuss incorporating as a city and being annexed to Bellevue. They had Bellevue and Renton addresses and sent their children to schools in Bellevue, Renton, and Issaquah.
In July 1991, Citizens for Coal Creek Community Study filed a petition to form a new city of 16,000 people and 8.3 square miles in size. Two thousand residents, unhappy with the incorporation idea, applied to the City of Bellevue to be annexed in five different parcels. By the time the Boundary Review Board approved the annexation proposal, almost half the new city had been annexed to Bellevue.
On November 2, 1993, the residents approved incorporation as the City of Newport Hills. Most incorporation efforts failed when first on the ballot, but residents appeared to feel an urgency because of annexation plans by Bellevue and Renton. But the area that Bellevue had annexed was also Newport Hills and incorporation supporters offered alternative names such as Newcastle and Cougar Mountain. King County planners called it "South Remainder" (Post-Intelligencer, November 8, 1993). Newcastle became an early favorite after the coal mining community that thrived there in the nineteenth and early twentieth centuries.
On March 29, 1994, voters selected a seven-member city council. Council members chose Tom Drummond as mayor and set about finding a city manager. City Hall was a storefront at 6969 Coal Creek Parkway. The new city officially took form on September 30, 1994. The council put the issue of a name change on the November 8, 1994, general election ballot and voters approved Newcastle as the city's new name.