In 1998, Seattle voters approved the Libraries for All bond issue, which provided for replacement or upgrade of all the branch libraries as well as a new Central Library. The International Style library building at 4th Avenue and Madison Street opened in 1960 and after almost 40 years of service, was at the end of its useful life. Koolhaas won a bid competition in May 1998 to submit a design for the new building.
Koolhaas stated, "It would be a pity [for the new library] to be as boring" as the buildings around it (Seattle P-I). He wanted the new building to accommodate books, but also many kinds of readers including the disabled and homeless people that frequent the library.
The old building was demolished in November 2001. The new Central Library opened on May 23, 2004.