Iranian President Mahmoud Ahmadinejad discussed the Syrian conflict with Egyptian counterpart Mohamed Mursi on Tuesday, in the first visit by an Iranian leader to Egypt in decades amid thawing relations.

Mursi, an Islamist who fiercely opposes Ahmadinejad’s Syrian regime allies, met the Iranian leader in Cairo airport after his arrival for the Organisation of Islamic Cooperation summit, footage on state television showed.

The two leaders discussed “ways to resolve the crisis and end Syrian bloodshed, without military intervention” and “ways to strengthen relations” between their countries, the official Egyptian MENA news agency reported.

Egyptian Foreign Minister Mohammed Kamel Amr said improved relations with Iran would not come at the expense of Gulf states, which accuse Tehran of plotting to undermine their regimes. “Egypt’s relations with any country will not be made at the expense of other countries’ security,” he told reporters. “We consider the security of Gulf states in particular a red line.”

Egypt and Iran severed full diplomatic relations after Iran’s 1979 Islamic Revolution, which opposed Egypt’s peace deal with Israel. No Iranian leader had visited Egypt since.

Ahmadinejad, who is on a three-day visit, will attend an Organisation of Islamic Cooperation summit in Cairo which opens on Wednesday, Iranian media said ahead of the trip.

After meeting Mursi, Ahmadinejad went to see Ahmed al-Tayyeb, head of the prestigious Sunni Muslim Al-Azhar institute. Ahmed al-Tayyeb told Ahmadinejad to not interfere in the affairs of Bahrain or the Gulf and to uphold the rights of his country’s Sunni minority. Tayyeb called for Muslim “unity” in a statement on Tuesday, before the meeting.

Before leaving Tehran, Ahmadinejad told reporters that during his visit he would work towards strengthening bilateral ties with Cairo. “I will try to pave the ground for developing cooperation between Iran and Egypt,” Ahmadinejad was quoted as saying by Iran’s official IRNA news agency. Without elaborating, he said the visit would “definitely influence the bilateral ties” between Tehran and Cairo.

Egypt has responded cautiously to Iranian efforts to revive ties since Mursi took power in June. Iran supports the regime of Syrian President Bashar al-Assad, while Egypt has been a leading voice urging his departure - along with regional heavyweights Saudi Arabia, Turkey and Qatar. “If Tehran and Cairo see more eye to eye on regional and international issues, many (issues) will change,” IRNA quoted Ahmadinejad as saying.

Tehran is committed to the survival of Assad and his regime. It has supplied financial aid and admitted to sending Revolutionary Guards military advisers to Damascus. But Egypt, despite its deep opposition to Assad, has tried to include Iran in regional diplomacy on ending the conflict, which has killed an estimated 60,000 people.

Egypt and Iran have taken opposite courses since the late 1970s. Egypt, under Mubarak’s predecessor Anwar Sadat, concluded a peace treaty with Israel in 1979 and became a close ally of the United States and Europe.