Rice was scheduled to meet with President Vladimir Putin, National Security Advisor Igor Ivanov, Foreign Minister Sergey Lavrov, former Prime Minister Yevegeny Primakov as well as Russian civic leaders in a bid to soothe tensions over major policy differences, particularly on U.S. missile defense plans for Europe.
She said Monday that now was a time for "intensive diplomacy" and that Washington is committed to working through the problems that also include Russia's threat to suspend a major military treaty and Moscow's opposition to a U.N. plan for Kosovo independence.
There is also growing U.S. concern about Moscow's treatment of its former Soviet neighbors and steps that Putin has taken to consolidate power in the Kremlin - seen as democratic backsliding as Russia prepares for presidential and parliamentary elections next year.
"I don't throw around terms like 'new Cold War,"' Rice said. "It is a big, complicated relationship, but it is not one that is anything like the implacable hostility" between the United States and the Soviet Union for a half-century after World War II.
"It is not an easy time in the relationship, but it is also not, I think, a time in which cataclysmic things are affecting the relationship or catastrophic things are happening in the relationship," Rice told reporters Monday as she headed here.
She noted that the United States and Russia are working together in numerous areas: on Iran and North Korea's nuclear programs, the global spread of weapons of mass destruction and efforts to achieve Middle East peace.
But her visit comes as the two nations have traded increasingly sharp barbs, despite ostensibly warm personal feelings between Putin and U.S. President George W. Bush, who spoke to each other just last week and are expected to meet at a summit of leaders in Germany next month.
A planned event Tuesday at which Rice and Putin were to be photographed together and make brief remarks was canceled by the Kremlin and a senior Russian diplomat warned the U.S. not to try to go it alone in world affairs.
In April, simmering Russian anger over U.S. plans to place missile defense components in Poland and the Czech Republic, both former Warsaw Pact members, boiled over despite Washington's pledges to cooperate with Moscow on the system.
Russia views the plan as an attempt to alter the strategic balance. Rice has dismissed such concerns as "ludicrous," but top Russian military officials have hinted the system might be targeted.
Last month, hours before the United States and its NATO allies met in Norway to discuss the matter, Putin threatened to suspend Russia's participation in a key treaty limiting military deployments in Europe.
Rice says that NATO and the United States want to keep the Conventional Forces in Europe pact alive but cannot unless Russia abides with its treaty commitments.
Russia views U.S. activity in its former sphere of influence with growing suspicion. Just last week, Putin denounced "disrespect for human life, claims to global exclusiveness and dictate, just as it was in the time of the Third Reich."
The Kremlin insisted that Putin had not meant to compare the Bush administration's policies with those of Nazi Germany, but the reference appeared to highlight Russia's annoyance at what it sees as U.S. domination of world affairs and meddling in Russian politics.
In addition to discussion of missile defenses, she said she would push the Russians on accepting a U.N. proposal for supervised independence for Kosovo, now a U.N.-administered province in Russian-allied Serbia, that Moscow has threatened to block.