On Monday, a ship carrying petrochemicals left Iran and headed west for Egypt.
It was the first act of trade in recent years between the two countries, but despite the embargo cooperation between Cairo and Tehran is said to have continued behind the scenes.
Iran and Egypt have followed an awkward relationship in recent decades.
The two countries have had no diplomatic relations since 1980, when Egypt offered Shah Mohammed Reza Pahlavi refuge following a revolution in Iran.
Egypt was tied to a Western embargo of Iran when Tehran was slapped with sanctions due to its nuclear activities until recently.
Now, the first shipment of Iranian oil to Egypt could mark a new stage in relations between the two countries.
"Iran has no limitations to sale of crude oil and oil products to Egypt and any official request will be considered when it is made," Iran's Press TV reported Roknoddin Javadi, managing director of the National Iranian Oil Company saying.
Egypt's new Suez Canal expansion could be opened to Iranian oil, traffic desperately needed after a difficult and disappointing launch to this hugely expensive vanity project.
The move comes at the same time as Egypt backs Saudi Arabia in its diplomatic battle with Iran.
Riyadh executed a popular Shia cleric on 2 January sparking outrage in Tehran.
Few would expect Cairo to turn away from its long-time ally regarding a dispute Riyadh has almost unanimous Arab support.
Egypt's President Abdel Fattah al-Sisi appears enamoured to leading Gulf states for their support following the 2013 coup, which overthrew Muslim Brotherhood leader Mohammed al-Morsi.
Cairo is also reliant on Gulf financial support and investment to help its flagging economy, which makes the issue of friendship with Iran a sticky point.
Yet behind the scenes, Iran and Egypt appear politically aligned on key regional issues.
Both countries seek "stability", which is often a misnomer for giving authoritarian regimes’ the sole right to use violence in the Middle East. One issue of apparent agreement is Syria and here Sisi appears keen to keep the status quo.
Sisi is said to be looking to bring Syrian dictator Bashar al-Assad back in favour with Gulf states, but with unsurprising little success.
During an interview with a Hizballah-linked channel, Assad said communication with Egyptian intelligence services has continued, according to Middle East Monitor.
The embattled president also acknowledged that Morsi - said to have always been mistrusted by Iran - had attempted to do Syria "harm".
Indeed, Morsi's support for the Syrian revolution was unquestionable.
Palestinian group Hamas which has been under siege by Israel and Egypt in Gaza has also tacitly condemned Damascus brutal repression of the Syrian people.
The group moved from its Damascus suburbs early 2012, after thousands of Syrians had been killed and distanced itself from the regime's main ally Iran.
Sisi clearly sees the groups opposed to Assad - be they secular or Islamist - as mirror images of the threats he faces at home.
Cairo's mass arrests and killing of opponents and activists are not dissimilar to the Syrian regime's own clampdown on dissenters during the early days of the revolution.
Sisi's talk of Egypt being under attack from "terrorists" very much mirrors the Assad's rhetoric and the emphasis on security answers to questions of domestic opposition are almost exact.
The militant violence in the Sinai was also a convenient scapegoat for Sisi.
As was the proliferation of extremist groups after Assad released thousands of jailed militants and filled Syria's dungeons with peaceful protesters.
Russia is also a convenient mutual friend for both countries, which is also seeking "containment" and "stability" in the Middle East.
Reactionary politics and opposition to the Arab Spring have brought Egypt, Iran and Syria together, even if they share very different allies and during an awkward time to be friends.