Dutch National Opera & Ballet is a young theatre with a long history. The plans for building a new theatre ran parallel to the plans for a new city hall. The first discussions held by the Amsterdam city council about building a new city hall and opera house go back to 1915. At that time, the plans were specifically for an opera house, since ballet was a relatively unknown art form back then.

Ideas for the site of the new city hall and opera house were continually changing, and the idea that both buildings could form a single complex only emerged much later. Sites considered for the new city hall were initially the Dam, followed by the Frederiksplein and finally the Waterlooplein.

In 1955, the city council commissioned the firm of architects Berghoef and Vegter to draft a design for a city hall on the Waterlooplein. The draft was approved, but in 1964 the council ended the association with the architects, as the final design was nothing like the original plans they had been shown. In 1967, a competition was held for a new design, with the Viennese architect Wilhelm Holzbauer emerging as the winner. Amsterdam's financial problems, however, meant that the plans for the new city hall were put on hold for several years.

The plans for the site of the opera house also made a tour around the city: the Museumplein, Frederiksplein, Waterlooplein, Ferdinand Bolstraat and finally once again the Waterlooplein. For a while there was even talk of a mobile opera house.

Engineer Bijvoet (associated with Holt architects from 1948) was commissioned in 1956 to design an opera house for the Frederiksplein. In 1961, he had to 'move' the design to the Ferdinand Bolstraat. Despite the city council’s approval of the plans in 1967, progress was so slow that Wim Kan, the renowned cabaret performer, remarked in 1971: "Come on lads, we've got to do something about that new opera house in Amsterdam: the model of it is about to collapse". Exponents and opponents shouted each other down, the action group 'Opera on the Ferdinand Bolstraat? 'Sol-di-mi-terop' (an organisation campaigning strongly against the opera house on that site) was formed, and the initiative committee 'Muziektheater NU' (Music Theatre NOW) organised a special evening in the Carré Theatre to give the project a boost. All these activities, however, had little effect.

Both projects had reached an impasse at the end of the 1970s, until in 1979 the architect Holzbauer proposed that the city hall and opera house could be combined in one complex. The Council took up this idea and put it to the government of the day. The response was positive and so it was decided to pursue the idea further. It had already been agreed that the Dutch National Ballet would also be one of the resident companies of the new theatre, alongside De Nederlandse Opera.

Engineer Bijvoet died at the end of 1979 and was succeeded by the architect Cees Dam. The 'Club van 100' was set up, and through its full-page advertisements this committee urged politicians to keep the momentum going for the combined City Hall and The Amsterdam Music Theatre. The City Council approved the design in 1980, and this was soon followed by approval from the Provincial Executive for Noord-Holland and the Crown in 1981.

Riots broke out as the first piles were driven into the ground. The protest was given the name: 'Van Stopera naar Slopera' (roughly meaning 'From building to demolition'). Construction work was postponed for a month before a definitive start could be made. The Amsterdam Music Theatre was officially opened on 23 September 1986 and the Amsterdam city council moved into its new city hall in September 1988. The famous Waterlooplein flea market, which had been temporarily moved to the Rapenburgerstraat, returned to the square next to the new city hall in the same year.