KK Skopje was formed in 1966 by a group of enthusiasts led by the club's first president, Mile Melovski.

KK Skopje lost and, due to leaving the field in Ivangrad, received a penalty of eight points for the next season.

KK Skopje got relegated again to the regional league and Taki Dzikov was selected to be the head coach.

The team debuted in the Yugoslav First Basketball League in the 1986–87 season with coach Lazar Lečić, who was previously head of their "eternal rivals" Rabotnički.

In the mid-1990s, MZT Skopje had a few successful runs in European competitions, the most memorable being the 1996–97 season when the team played in the Raimundo Saporta Cup.

In this period, MZT was led by coach Aleksandar Knjazev, and the team defeated Real Madrid, Benfica, and Ratiopharm, and has therefore qualified for the 1/16 finals, without losing one match at home in Jane Sandanski Arena.

The home form continued when MZT Skopje managed to defeat Porto in Jane Sandanski.

But the win was not enough, as Porto won at home by a bigger margin, ending MZT Skopje European season.

In the next few seasons, MZT Skopje had a marginal role in the European cups, playing against teams like Žalgiris, ASVEL, Cholet, Split, and others.

Two weeks before the beginning of the season, MZT Skopje was left without players, coach, youth school, and sponsors.

A day before the deadline for application of teams for the current championship, the Family Aerodrom fan group organized a march in order to save the club.

Due to the financial problems of the club, it had the worst season since the independence of Macedonia, so MZT Skopje had to play in the play-out to secure its place in the league.

In the next season, 2010–11, the club got new sponsors, there was a complete reorganization of the management set, and the junior school was reactivated, which had been defunct for eight years.

After all the turmoil and upheavals in the past, after a long time, KK MZT Skopje formed a team which became a favourite for winning the first league title since its existence.

Feni was also an opponent in the league finals; Aerodrom won the series 4–1 and became a champion of Macedonia on May 2, 2012, for the first time in its history.

The newly named coach Vlada Vukoičić, who replaced Aleš Pipan, brought some new players, including Stefan Sinovec, Uroš Lučić, Justin Reynolds, and Macedonian international Aleksandar Kostoski.

The team was drawn in the group with UNICS, Banvit, Maccabi Haifa, VEF Riga, and BC Kalev/Cramo.

The elimination from the Macedonian Cup in the semifinals by Kozuv and the next-to-last place in the ABA League meant resignation for Jončevski.

After mixed performances in the ABA League regular season, the head coach Aleš Pipan was replaced by Aleksandar Jončevski.

In domestic competitions, MZT won another cup and league "double", becoming the champions for the fifth time in a row.

In the ABA League, the team defeated Krka in the decisive match in the last part of the season and was thus saved from relegation, finishing in 13th position.

In February 2018, MZT won its nine Macedonian Cup trophy with a win over Rabotnički in the final tournament in Kavadarci.

In the 2018–19 ABA League Second Division, MZT Skopje, coached by Gjorgji Kočov, finished in third place during the regular season.

In the play-offs, the club defeated Spars Sarajevo 2–0 to reach the final, where they lost to Sixt Primorska (3–0).

On 14 February 2013, MZT Skopje held their last training in Jane Sandanski, with more than a thousand fans attending.