The zoo was founded in 1926 by a three member commission led by Stanko Karaman. When it opened, the zoo covered only 4 hectares (9.9 acres), and exhibited only a few animals which it had received as gifts. With a decision by the Skopje city council in 1965, and the new town zoning in 1966, the zoo was expanded to its current size.
Over the years the zoo received much criticism for the living conditions of its animals. The only elephant ever held by the zoo died at age 23 less than a year after being transferred from the Belgrade Zoo, and the chronically depressed lone Chimpanzee Koko was transferred to the AAP Primate Sanctuary in 2009.
However, in 2008 the City allocated Denar 42 million in funds to improve the zoo, and the zoo started working with the European Association of Zoos and Aquaria (EAZA) to improve conditions and bring the zoo up to modern standards. By 2010, 18 new enclosures had been built, 85% of the older exhibits at the zoo had been renovated, and the zoo was a candidate member of the EAZA.