Built with white stone from Brač island, and opened on 24 January 1954, by mid 2000s the stadium began showing signs of structural deterioration. Architect Mihajlo Janković, was awarded the Belgrade's October award for architecture, the highest city award at the time, for the Tašmajdan project. Originally, the sports complex started as the ice factory, where people could buy the so-called "hygienic ice".
Some of the best known happenings in the venue include: EuroBasket Women 1954, first Miss Yugoslavia contest in 1957 (won by Tonka Katunarić), 1957 World Women's Handball Championship (the inaugural world women championship), concerts of Alexandrov Ensemble in 1958 and later in the 1960s and 1970s of Mazowsze, Elton John, Ray Charles and Tina Turner and ice hockey matches with over 10,000 spectators. Yugoslav national tennis team played the Davis Cup matches in 1956 in Tašmajdan and the curiosities held in the facility include the chess with live figures, the football matches played by the Zastava 750 cars and the first Spanish corrida in Europe outside of Spain, when Luis Miguel Dominguín performed. Tašmajdan hosted the first FINA World Aquatics Championships in 1973.
After the 1977-78 season, the ice skating rink was dismantled in March 1978. Bad conditions of the facility in the 2000s led many public personalities in Belgrade (Cane Kostić, Neda Arnerić, Branko Cvejić) to urge the city government to do something about it. In mid-April 2009, the initiative called "Taš je naš" (Serbian Cyrillic: Таш је наш; "Taš is ours") was held to draw public attention to the sad state of the crumbling facility. In the summer of 2009 the stadium was closed to the public due to the impending reconstruction. An extensive RSD550 million renovation began in September 2011. Originally, the reconstruction was to be finished in December 2012, then was postponed to 2014 and was finally completed in 2016. As the object is under the protection, the conceptual solution for the reconstruction had to fully preserve the original author's concept. Since 2016, the ice skating rink became operational again during the winter. It covers 1,800 m2 (19,000 sq ft) and though it worked only for less than 60 days in 2016, it had 30,000 visitors.