The shake-up could become a test of Zelenskiy's political authority as Ukraine's fight against Russia's full-scale invasion approaches fuur-and-a-half years.
Zelenskiy has remained in office under martial law because wartime elections are prohibited and has periodically reshuffled his government.
The political furore took place against a backdrop of unceasing Russian aerial attacks.
Two people were killed and five others were wounded, including a child, when Russian missiles hit the capital, Kyiv, overnight, Ukraine's Emergency Service said.
Ukraine's parliament approved Serhii Koretskyi, the head of state energy company Naftogaz, as the country's new prime minister.
Zelenskiy nominated Koretskyi, citing his record in the energy sector and arguing that he was best placed to help prepare Ukraine for another wartime winter, when Russian attacks on the power grid intensify.
Outgoing Defence Minister Mykhailo Fedorov, 35, is considered to be a moderniser whose technological expertise is credited in part with a significant improvement in Ukraine's military performance in recent months against Russia's bigger army.
He was leaving the government after just six months in the post.
Zelenskiy did not publicly give a reason for Fedorov's anticipated exit and did not immediately name a successor.
Unconfirmed Ukrainian media reports said that Fedorov had a strained relationship with General Oleksandr Syrskyi, the commander of Ukraine's armed forces.
Syrskyi, 60, is credited with initially organising the defence of Kyiv in February 2022, and seven months later masterminded a successful counteroffensive in the Kharkiv region.
The mostly young protesters shouted Fedorov's name and made crude remarks about Skryskyi.
They chanted, "Skryskyi go away!" and "A European army for a European country!"
The Ukrainian military has rallied under Fedorov's guidance, slowing Russia's frontline advance to a virtual standstill and causing fuel shortages in Russia through long-range strikes, Western officials and analysts say.
Zelenskiy's decision to fire him despite that record has dismayed many people.
As well as Kyiv, demonstrations were also held in other cities across Ukraine, including Dnipro in the centre of the country and the southern port city of Odesa.
The deputy commander of Ukraine's air force, Colonel Pavlo Yelizarov, quit over Fedorov's dismissal.
Fedorov's removal would weaken Ukraine's air defences and lead to greater loss of life from Russian missile and drone attacks, Yelizarov said in his resignation letter posted on social media.
"I believe that the dismissal of Mykhailo Fedorov is a great evil for the country's defence capability," he wrote on Facebook.
Zelenskiy swiftly reversed course in July 2025 when large street protests broke out over a new law that would have curbed the independence of the country's anti-corruption watchdogs.
The outcry threatened the stability of his leadership for the first time since Russia's all-out invasion, which began on February 24, 2022.
Before he became defence minister in January, Fedorov was the head of Ukraine's digital transformation policies and seen as a moderniser.
He won public popularity by spearheading Ukraine's speedy development and deployment of drone technology and introducing several successful e-government platforms.
He also promised sweeping military reforms, saying after he took over that the military had faced about 200,000 troop desertions and draft-dodging by about two million people.
Zelenskiy did not formally announce Fedorov's departure.
However, Fedorov confirmed his dismissal and listed his achievements in office in social media posts late on Wednesday, after days of unconfirmed Ukrainian media reports that he was on his way out.
