David Miliband says both the UK and Russia want a "prompt response " from Iran
Foreign Secretary David Miliband has said the UK and Russia would not "paper over our differences" but these would not block co-operation between them.
He met his Russian counterpart on the first visit to the country in five years by a UK foreign secretary.
Mr Miliband said greater cultural and business links between both countries reflected increased "common ground".
Relations reached a low after the murder in London of Russian emigre Alexander Litvinenko in November 2006.
But Mr Miliband insisted the UK's continued demand for the extradition of the main suspect in the killing would not block co-operation on other issues.
The foreign secretary said the talks had been "substantive and productive" and marked by "mutual respect".
Mr Miliband said both wanted a "prompt response" from Iran over international proposals about its nuclear programme.
The International Atomic Energy Agency (IAEA) had suggested Iranian authorities send uranium abroad for further processing.
'Eye to eye'
Bridget Kendall, BBC diplomatic correspondent
Not since July 2004 has a British Foreign Secretary been to Moscow - an extraordinarily long time, given the volume of trade between the two countries and the global problems they are both concerned about.
But relations were plunged into a freeze following the tit for tat diplomatic expulsions that followed the Litvenenko murder.
On the eve of Mr Miliband's arrival in Moscow the Russian ambassador to London was still blaming Britain for an "anachronistic" attitude and "artificial barriers" which stood in the way of improved relations.
Both countries agree they need to work together. But neither side seem to think they'll find a way past their deep seated disagreements.
He added that, although there were differences between the two countries, there had been a "genuine search for common ground and common action".
Mr Miliband told reporters: "The cultural and business links that are growing, I think, are testimony to the importance of the UK-Russia relationship.
"That is reflected now at governmental level - not just on issues of the economy and foreign policy, but also on energy, climate change and other issues."
He continued: "We don't paper over our differences but we don't allow them to block co-operation".
Sergei Lavrov, Russia's foreign minister, said he was grateful to Mr Miliband for the "positive, productive talks" but insisted it was impossible to fulfil British demands on the Litvinenko case as the Russian constitution forbade extradition of its citizens.
He added: "The demands that we basically change our constitution are absolutely unrealistic."
Mr Miliband had met Sergei Lavrov for dinner and informal talks ahead of the meeting.
Discussions were expected to cover Iran, the Middle East and Afghanistan.
According to BBC diplomatic correspondent Bridget Kendall, a senior diplomat has indicated the main focus will be on issues where Russia's collaboration is needed internationally - over Afghanistan, and over the question of Iran's nuclear programme.
The aim, said the diplomat, was to be clearer about Russia's position on Iran, and whether if current negotiations with Tehran failed, Russia would be prepared to adopt a tougher position.
The last British foreign secretary to visit Russia was Jack Straw in 2004. But Prime Minister Gordon Brown has spoken frequently with Russian president Dmitry Medvedev at international summits.
Ahead of his arrival, Mr Miliband said the UK still did not always "see eye to eye" with Russia but acknowledged it was a world power and an important trading partner.
Writing on his blog, Mr Miliband said: "We share the same global challenges and it is important that we work on them together.
"The wealth of people-to-people contacts and the dynamic business links which have grown between Britain and Russia over the last 20 years make political engagement all the more important."
The Foreign Office said Mr Miliband would meet a range of politicians, business leaders and representatives of civil society before returning home on Tuesday.
Relations between Britain and Russia took a turn for the worse after former Russian security agent Mr Litvinenko was poisoned.
Moscow refused UK requests to extradite chief suspect Andrei Lugovoi and several tit-for-tat diplomatic expulsions took place as the row rumbled on.
The situation worsened further when Moscow ordered the closure of British Council offices due to alleged tax irregularities.
There have also been tensions over spying claims and a struggle over BP's interests in Russia.
Ahead of the meeting, a group of MPs urged Mr Miliband to raise human rights issues with Mr Lavrov.
A letter signed by MPs including Labour's Tom Watson, Tory Julie Kirkbride and Liberal Democrat Julia Goldsworthy, highlighted concerns over the fraud trial of former oligarch Mikhail Khodorkovsky, which his supporters have claimed was politically motivated.
Read some of your comments about this story:
It's vital we maintain good relations with a country that will probably grow in importance over the coming years. They are a difficult bunch to deal with, but so are the British and the two countries have far more in common than either will admit. David Blake, London, UK
In my point of view, relations are very unlikely to be improved by the one visit of UK Foreign Secretary. I think it will take a few generations for Russia to leave the soviet roots and take the road to the democracy, and then I think relations could turn to a new side with the whole "West World". Nowadays communist past plays a big role in the relations with western countries that are very careful of investing money to Russia. Dmitry, Korolev, Russia
It is very good news that the British foreign secretary had the courage to go to Moscow and had so good a reception. Russia is the one great European nation of the nineteenth century Concert of Europe, still outside the new Europe. Europe cannot be complete without Russia and the enormous contribution Russians have made to our common European culture in music, ballet, literature, religion and art. The Cold War is over, we need Russia and Russia needs Europe. Thank God for David Miliband's imaginative leadership. John Hunter, Carnforth, UK
Is Mr Miliband really that naive to trust the wild Bear? Think again. Willy, New Milton, UK
The talks are constructive and positive, and Mr Miliband is going the right way about it by not complicating the issues with the differences the both countries have between us. The one thing the foreign secretary has as a bonus when talking to the Russian political, and business people is that he was never caught up with the MPs expenses, and supported the Prime Minister in his hour of need, which makes him a person of trust, and the Russians can believe in what he says is true, and is a good foundation to bond the two countries together, for the good of this wonderful planet we all live in, and need strong and sensible people if it is to survive! Thomas Henry Carver, Gateshead, UK
This page is best viewed in an up-to-date web browser with style sheets (CSS) enabled. While you will be able to view the content of this page in your current browser, you will not be able to get the full visual experience. Please consider upgrading your browser software or enabling style sheets (CSS) if you are able to do so.