It's "very unlikely" the British-built Mars rover, Rosalind Franklin, will launch this year.
The European Space Agency (ESA) says the project is now at risk because of the worsening diplomatic crisis over the war in Ukraine.
The robot is part of a joint venture with the Russian space agency.
It's due to launch on a Russian rocket in September and land eight months later using Russian hardware, but this cooperation may now be hard to justify.
ESA said in a statement on Monday that "sanctions and the wider context" had put a big question mark next to Rosalind Franklin, which is named after the British scientist who co-discovered the structure of DNA.
"We deplore the human casualties and tragic consequences of the war in Ukraine," the agency stated.
"We are giving absolute priority to taking proper decisions, not only for the sake of our workforce involved in the programmes, but in full respect of our European values, which have always fundamentally shaped our approach to international cooperation."
At the weekend, the Russian space agency Roscosmos announced it would be suspending flights of its Soyuz rockets from the European Kourou spaceport in French Guiana, as retaliation for EU economic sanctions.
Untangling Decades Of Space Cooperation
The aspiration is that space sits well above any conflicts happening on Earth below.
And for decades, Russia and the West have found room to co-operate, even when tensions were high during the Cold War and Crimea crisis.
But the invasion of Ukraine marks a turning point, and the idea of continuing business as usual in the skies above has become harder to contemplate. However, untangling decades of cooperation will not be easy.
If the ExoMars programme is suspended, does this mean the spacecraft is put in storage and then wheeled back out again for launch once the crisis comes to an end?
Or does it mean the elements that Roscosmos have made - the landing system - are redesigned and rebuilt without Russia's involvement?
These sorts of questions will be being asked right now for every western mission involving Russia.
The trickiest problem though is the International Space Station.
The infrastructure on the orbiting outpost is so entwined that Russia would struggle to operate there without the other space agencies - and vice versa. It may be that the ISS remains a beacon of space cooperation - because there is no alternative.
Rosalind Franklin has only a limited time to launch to Mars this year - just a short, 10-day window in late September and early October.
This narrowness is governed by the alignment of the planets.
If the robot misses the window, it must wait another 26 months before getting another go.
The rover itself is built, as is its Russian descent and landing mechanism, known as Kozachok.
Some technical issues still need to be resolved, but there is every confidence the pair could reach the launch pad in time - given the opportunity.
In the current climate, however, the sentiment is not positive.
In the UK's House of Commons last week, the Prime Minister Boris Johnson said space cooperation with Russia was difficult to justify.
"I must say that hitherto I have been broadly in favour of continuing artistic and scientific collaboration but in the current circumstances, it's hard to see how even those can continue as normal," he told MPs.
Rosalind Franklin is the second stage in a two-part space programme known formally as ExoMars.
The first part is a satellite that was launched to the Red Planet in 2016. It is studying the planet's atmosphere and is due to act as a telecommunications relay platform for Rosalind Franklin when it arrives.
Within Esa, the UK has been the second largest contributor to the ExoMars programme (behind Italy), having invested over €300m (£250m), with most of that geared towards leading the development of the rover.
Another non-Russian rocket could be found to launch the robot in 2024, but sourcing western hardware to place the vehicle on the surface of the planet might not be so straightforward.
The expertise exists in Europe - and especially in the US - to build such a descent and landing system, but it would surely take more than two years to design, build and test, meaning Rosalind Franklin would be pushed even further into the future.
This would inevitably lead some to question its continuing relevance as a scientific endeavour.
The robot's objective is to drill up to 2m into the ground to look for traces of life. No other planned Mars mission has this goal.
ESA's desire to send a six-wheeled vehicle to the Red Planet is a long-running saga.
The idea was first approved by member states as far back as 2005, with a launch pencilled in for 2011.
Indecision, technical woes and funding shortfalls subsequently saw the project miss launch window after launch window.
Neither the UK Space Agency nor Airbus UK, who assembled Rosalind Franklin, wanted to add to ESA's Monday statement.