At least two videos published on YouTube earlier this week show burly, heavily armed soldiers with no insignia in the city, which has been gripped by pro-Moscow protests.
In one of the videos onlookers can be heard shouting 'Blackwater! Blackwater!' as the armed men, who wear no insignia, jog through the streets.
Donetsk was this week the scene of civil unrest as pro-Russian elements among its citizens seized control of the regional administration headquarters and another government building.
Yesterday thousands of people gathered in the city centre waving Russian flags and calling for a referendum to determine the status of the strategically important coal-mining region.
Both the videos which purport to show 'Blackwater' mercenaries in Donetsk were uploaded last Monday, with their descriptions written in Russian.
The context of the videos is not clear, but it appears that the armed men had turned up at a street protest against the new regime. They wander around brandishing their weapons before suddenly fleeing the scene as passers-by shout 'Blackwater! Blackwater!'
Since the videos emerged, Twitter has been alive with speculation that mercenaries linked to Blackwater, now known as Academi, are active in Ukraine, helping to prop up the embattled new pro-western government.
And a Russian diplomat in Kiev told the Interfax news agency on Wednesday that 300 employees of private security companies had arrived there.
'These are soldiers of fortune proficient in combat operations. Most of them had operated under private contracts in Iraq, Afghanistan and other states,' the source said. Interfax reported that the diplomat did not disclose the nationalities of the mercenaries but said, 'Most of them come from the United States'.
Asked whether the soldiers seen in the videos could be from Academi, Dr Nafeez Ahmed, a security expert with the Institute for Policy Research & Development, said: 'Difficult to say really. It's certainly not beyond the realm of possibility - Academi have been deployed in all sorts of theatres.
'I think the question is whether the evidence available warrants at least reasonable speculation.
'On the face of it, the uniforms of the people in the videos are consistent with US mercs - they don't look like Russian soldiers mercs. On the other hand, why run around in public making a show of it?'
He added: 'Of course the other possibility is it's all Russian propaganda.'
Any suggestion that a U.S. mercenary outfit like Academi had begun operating in the country could give Russian president Vladimir Putin the pretext for a military invasion.
The Russian parliament, the Duma, has already voted to give Putin the authority to take action in the country, where the pro-Russian president Viktor Yanukovych was last month ousted after mass protests in the capital, Kiev.
Pro-Russian forces have already seized control of the southern Ukrainian province of Crimea, although the Kremlin denies that the thousands of heavily armed, well-equipped men that have appeared there are under its control.
Last month a report in the Daily Beast claimed that 'informed sources' in Moscow had said the troops belong to Vnevedomstvenaya Okhrana, a private security contracting bureau similar to Academi that is close to the Kremlin.
The videos which emerged this week come amid reports in Russian media which claimed that 300 'strong' men had arrived at Kiev's Boryspil airport carrying military-style bags.
Reports speculated that they were being sent to regions in eastern and southern Ukraine where Russian-speaking and ethnic Russian groups posed a secessionary threat to the new government.
Blackwater was founded in 1997 by former U.S. Navy SEAL Erik Prince and were one of several private security firms employed by the U.S. government to protect its diplomatic missions overseas.
With the outbreak of the Iraq war in 2003 the company's operations expanded and its revenue mushroomed, but a string of controversial killings by its personnel led to a rebranding, first to Xe and then to Academi, its current name.
As well as acting as security contractors, Blackwater are seen by some as a private army that can promote U.S. interests without official military involvement.
Technically they are a multinational company and can by hired by anyone, but the board of directors includes a number of U.S. establishment figures including John Ashcroft, the former Attorney General, and former NSA chief Bobby Ray Inman.
If Blackwater are present in Ukraine, it would make most sense for them to be deployed in the country's east and south, where pro-Russian protesters raised the Russian flag over the regional parliament last Saturday.
It remained in place until Thursday when Ukrainian police regained control of the building without any resistance.
Donetsk, home city of deposed president Yanukovich, has seen the most persistent pro-Moscow demonstrations in a wave of protests that have erupted across southern and eastern cities.
MailOnline contacted Academi for comment, but there was no reply.
Comment: If you still have any lingering doubts regarding U.S. intentions in fomenting "regime change" in the Ukraine see:
Former CEO reveals Blackwater worked as 'virtual extension of the CIA'
Imperial Hubris: Ukraine as a 'regime change' too far for the American Empire
RT exposes the hypocrisy of U.S. intervention in Ukraine and elsewhere: Ukraine 'revolution' followed leaked CIA regime change manual to the letter