It was made from Indiana limestone, featured an imposing façade, and followed French Renaissance designs.

[1][2] The building opened on November 25, 1895 with the Broadway debut of Excelsior, Jr., with over 30 performers from Europe appearing.

[4] The venues were sold separately, with the Music Hall becoming the New York Theatre, which became part of the Loew's movie theater chain in 1915.

After the old venues were demolished, architects Thomas W. Lamb and Eugene De Rosa designed a new building on the site which included a new Criterion Theatre cinema, the International Casino nightclub, and retail space.

In the early 2000s, Toys "R" Us built a flagship store in the building, leading to the closure of both the cinema and the live theater venues.

[14] The multilevel store featured a 60-foot in-store Ferris Wheel and an animatronic T-rex among its attractions.

[16] In July 2016, during the construction of the Gap and Old Navy flagship store, remnants of the original Olympia were found under the floors.