Just after becoming the first-ever successful, democratically re-elected President of Russia, Boris Yel'tsin ambitiously called for creating, within the next year, a new ideology that would reflect the new state of affairs in Russia—in essence, he was calling for “re-imagining,” or reinventing, the foundations upon which Russian national community is based. With this directive, Yel'tsin was confirming something that had already become clear to many observers of Russian politics: post-Soviet Russian political life not only continued to resist democratization and pluralism, but also appeared to exhibit signs of discomfort without an officially-sanctioned ideological reference point by which the political players could set their compasses. The Kremlin's quest for a restoration of Russia's credibility as a great power included serious consideration of religion, specifically Russian Orthodoxy, playing a leading role in helping to reformulate an ideology acceptable to diverse communities within Russia in order to replace the now-defunct Marxist–Leninist ideology of the Soviet state. The old French adage “plus ça change, plus c'est la même chose” seems particularly appropriate for the new Russia in its efforts to regain credibility as a great power, along with the prestige and respect to which it had become accustomed. This article examines the dynamics of the Russian search for a new ideology in order to help restore its credibility as a great power, as suggested by Yel'tsin's call for a new “national idea.” But the search for a new ideology began well before Yel'tsin made this statement, and, therefore, the following discussion focuses on the interplay between religion and politics in this quest, covering the first five years of a reconstituted, post-Soviet Russia, that is, the time period roughly from the collapse of the Soviet Union up to the Duma (parliament) elections of December 1995 and the two-stage presidential elections of June-July 1996.