The sun beat down on protesters as they gathered in the center of the city in the early afternoon.
At a sound stage set up by opposition party the Social Democrats (SDSM), techno remixes streamed from large speakers. They included snippets from dozens of recordings leaked by the SDSM in recent months.
Many of the tapes, which have been aired by Zaev over a series of more than 30 press conferences since February, appear to feature senior officials from Prime Minister Gruevski's cabinet conspiring to undermine its opponents and cover up murders.
Zaev has accused Gruevski of collaborating with former counter-intelligence chief Saso Mijalkov to wiretap the conversations of 20,000 journalists, activists, politicians and ordinary citizens.
His dramatic press conferences have centered around what Macedonians have called "bombs" – revelations of alleged vote-rigging and interference with the judiciary orchestrated at the highest levels of government.
Today marked the climax of months of unrest and political jostling, including protests last week and the resignation of three senior officials, including Mijalkov. Within an hour of the start of the protest, thousands had gathered. They held up Macedonian and Albanian flags alongside each other, a gesture to show solidarity between the ethnic groups. Last week, 18 people were killed in a gun fight which authorities said took place between ethnic Albanian guerillas and armed police in the northern city of Kumanovo.
The international community has looked on with growing concern, with some fearing wider implications for the region. European Union (EU) rapporteur on Macedonia, Ivo Vajgl, told the Guardian that the Kumanovo incident showed poor control of groups seeking to destabilize countries.
Special police forces lined up to guard the government building behind a temporary fence, while armored vehicles and police in protective gear congregated in the street behind.
Zaev had appealed for calm in the run-up to to the protests and, accordingly, a group of activists wearing red shirts lined up in front of police to insulate the crowd from clashes.
By mid-afternoon, as many as 40,000 protestors roamed streets close to the government building chanting slogans such as "Without justice, there is no peace", and "Down with the dictatorship". The sprawling crowd included not only SDSM supporters but representatives from other opposition parties, civil society groups, academics and students alongside unaffiliated citizens.
Protest organizers have made demands for a transitional government to replace Gruevski's cabinet until free and fair elections can be held.
"The young people of Macedonia have awakened from their slumber," said 21-year-old law student Edina Zekirovic. "I am here because I oppose our government. But I believe that the opposition is not very different from them. We don't have democracy in Macedonia – it's only a facade."
By 5.30pm, protesters began to disperse. Some, however, have camped out in front of the government building saying they will not go home until Gruevski resigns.
Gruevski, who denies wrongdoing, has announced counter-protests in support of his party, the VRMO-DPMNE, to take place tomorrow.
He accuses Zaev of attempting to mount a coup in collaboration with foreign intelligence service, and says the tapes were cut and edited to incriminate officials.
Zaev's latest "bomb"
The protest came a day after Zaev's latest conference, on Saturday. About 100 people squeezed into the SDSM HQ, where party members stood in front of their banner, awaiting their leader.
Zaev arrived to loud applause. Some attending the conference wore badges bearing the face of Gruevski with a red line through it.
Zaev started his speech by accusing Gruevski of "fake patriotism". He then proceeded to play a series of recordings which appeared to feature Gruevski negotiating with Minister of Foreign Affairs Antonio Milososki and Saso Mijalkov over changing the official name of Macedonia (the Former Yugoslav Republic of Macedonia, or FYROM).
Macedonia has been embroiled in rows since its creation in 1991 over the small country's name, which has created tensions with the neighboring Greeks.
Some of the suggestions featured on the tape included "Northern Macedonia" and "Upper Macedonia".
By Igor Spaic in Skopje
