Russian authorities said there were no survivors.
Mr Utkin, believed to be a special forces and military intelligence veteran, has been described as a neo-Nazi who had fought in Chechnya and Ukraine and had ties to Russia’s elite.
It was reputedly Mr Utkin who chose the name Wagner, after the German composer admired by Adolf Hitler. He is thought to have used it previously as an intelligence code name.
Rarely seen in public, he was sanctioned by the US, UK, EU and Canada for his alleged role in Wagner operations. European officials said he was “responsible for co-ordinating and planning operations” in Ukraine.
An EU sanctions listing said he was “personally present on the combat field in Ukraine” during fighting in the country’s east, before Russia launched its full-scale invasion in February last year. The US called him a "founder and leader" of Wagner.
Anecdotal reports have said Mr Utkin had his men wore field caps modelled on German uniforms of the Second World War and would greet subordinates by saying “Heil”.
Russia experts say Mr Utkin, 53, earlier fought in the Chechen wars and with private armies known as the Moran Security Group and the Slavonic Corps, before helping to set up the Wagner Group in 2014.
According to the Centre for Strategic and International Studies, he was involved in a failed Slavonic Corps operation in Syria that ended with the group being disbanded.
Once involved with Wagner, there were reports of intercepted phone calls between Mr Utkin and senior figures in Russia’s armed forces and military intelligence service.
In 2016 he attended a Kremlin reception as a recipient of the Cavalier of the Order of Courage, although Russia denied any knowledge of his mercenary links. He had not been seen in public since.
Also close to Mr Prigozhin, it was announced in 2017 that Mr Utkin had become general director of the mercenary leader’s Concord catering business, which at one time supplied the Kremlin.
It was in a statement via Concord last year that Wagner finally came out of the shadows, with Mr Prigozhin admitting his role in setting up and leading the private army.
As Wagner fell out with Russia’s top brass over equipment shortages and the mounting death toll of the war in Ukraine, Mr Utkin appeared to take Mr Prigozhin’s side.
When Kremlin ally Adam Delimkhanov publicly took aim at Mr Prigozhin, Mr Utkin leaped to the mercenary boss’s defence with a post on Telegram scolding Mr Delimkhanov for using overfamiliar language.
And when Mr Prigozhin marched his mutinous troops to Moscow in June, there were reports that Mr Utkin was at the head of a 5,000-man convoy that approached the capital’s outskirts by road.
The open rebellion against President Vladimir Putin looks to have cost the two men their lives. Western pundits and officials all the way up to US President Joe Biden were quick to speculate about foul play, given the fates that have often befallen Kremlin critics.
The plane, an Embraer SA Legacy 600, was cruising normally en route from Moscow to St Petersburg until it suddenly behaved erratically and plunged, according to flight-tracking data. Video from the scene showed the plane dropping from the sky.
One Kremlin loyalist, political scientist Sergey Markov, sought to divert blame from Moscow by suggesting Ukraine was behind the “murder of Prigozhin and Utkin”.