Russian President Vladimir Putin's visit to Israel this week is the first by any Russian or Soviet head of state.
Jewish cemeteries have been vandalised by anti-Semitic Russians
But despite a sea change in relations there are still obstacles to this new-found friendship.
Anti-Semitism that ran deep in the former Soviet Union has resurfaced in recent years in Russia.
Meanwhile Russia is one of a quartet of powers - together with the European Union, the United States and United Nations - that has been pursuing diplomatic initiatives to help solve the Israeli-Palestinian conflict.
The diplomatic editor of the Jerusalem Post, Herb Keinon, told BBC World Service's Analysis programme that initially Russia's involvement was described as a "me too" phenomenon - but this has changed.
"Now I think they want to play a more predominant role," he added.
To do this Russia must confront its complex past relationship with the Middle East - and Israel in particular.
The Soviet Union was one of the first to recognise the state of Israel in 1948.
But Moscow then swiftly changed course. It aligned itself with Arab nationalist regimes and severed diplomatic relations with Israel following the 1967 six-day war, subsequently supporting Palestinian militants.
This changed again, however, following the collapse of the Soviet Union in 1991.
President Putin attended ceremonies at Auschwitz in January
"At least covertly, the KGB and Russian foreign agents were very active in supporting the PLO and Arab militant groups in a proxy war against the West and its allies," said Andrew Jack, author of Inside Putin's Russia.
"Under Putin in particular - and starting under his predecessor Boris Yeltsin - there was much more of an attempt to establish a rapprochement with Israel to establish more friendly relations with the West."
He explained that much of the reasoning behind this was to do with Mr Putin's desire to be an iconic leader to Russians worldwide and have an impact on world politics.
However, Mr Putin's historic visit means he is likely to come under pressure from Israel's Prime Minister Ariel Sharon over a number of issues.
Russia remains a supplier to Iran's nuclear programme, and in January agreed to sell sophisticated anti-aircraft systems to the Syrian government - two things Israel is very concerned about.
And Mr Keinon added that along with these issues, Israel would also voice concern about Russian anti-Semitism.
There has been a resurgence of anti-Jewish feeling in Russia.
One of the most public displays came in February, when a letter was sent to Russia's prosecutor-general. Signed by hundreds of people, including 19 members of the Duma, it claimed that a centuries-old Hebrew text incited violence.
The letter also compared Judaism to Satanism, and accused Jews of ritual murder. It further called for Jewish organisations in Russia to be investigated and banned.
'Public enemy number two'
However, Ibrahim Berkowitz, executive director of the Federation Of Jewish Communities Of The Former Soviet Union, said that Mr Putin had tried to distance himself from these outbursts.
"Putin's administration is very strong against any acts or forms of anti-Semitism, and President Putin has mentioned many times," he stated.
Mr Sharon is concerned about Russia's ties with Iran and Syria
"At the same time these letters do concern us. We are happy that the government is strongly with the Jewish community and against any form of anti-Semitism - at the same time the Jewish community is growing.
"Jewish life is blossoming, not only in Moscow and St Petersburg but across the country."
Meanwhile Moscow-based historian Georgy Mirsky, of the Institute for World Economy and Public Relations, said that "public enemy number one" was no longer the Jews, but people from the Caucasus region - "Chechens, Azeris, and the rest of them.
"So the Jews are enemy number two."
However, he also pointed out that a recent poll showed that a third of Russians were in favour of officially restricting Jews and preventing them from holding any governmental or cultural positions.
But Herb Keinon stressed that things were not so bad that they could cripple relations.
"Israel doesn't see this as an Israeli-Russian issue - Israel does not view the Russian government as an anti-Semitic government," he said.
"Israel does not see Putin as an anti-Semite - on the contrary, it sees Putin as a man who has proven in the past that he wants to fight anti-Semitism.
"So they see this as something they can do together."