In early February 2004, C1R began airing television adverts that announced a submission period where interested artists and composers could submit their proposals for an internal selection. On 10 March 2004, C1R announced that Julia Savicheva had been selected to represent Russia. Other artists that sent entries for consideration included Smash!!, Anastasia Stotskaya, Dima Bilan, Reflex and Avraam Russo. The jury panel that selected the Russian entry included Konstantin Ernst (general manager of C1R), Aleksandr Fifeman (general producer of C1R), Marina Danielan (service manager of C1R), Yuriy Aksyuta (music director of C1R), Vladimir Matetsky (composer) and Valeriya (singer).
On 19 March 2004, it was revealed that Savicheva would sing the song "Believe Me" at the 2004 Contest.
For the Eurovision Song Contest 2004, a semi-final round was introduced in order to accommodate the influx of nations that wanted to compete in the contest. Since Russia placed 3rd in the previous contest year, Russia automatically qualified to compete in the final along with the Big Four countries and nine other nations that were also successful in the 2003 Contest. 22 semi-finalists competed for 10 spots in the final, joining Russia among the 14 pre-qualified nations. On 23 March 2004, Russia was drawn to perform 14th in the final on 15 May 2004, following Belgium and preceding a slot allotted for a semi-finalist qualifier, which was ultimately filled by Macedonia.
The Russian performance featured Savicheva performing an athletic routine with four male dancers, choreographed by Kamel Ouali. After the voting concluded, Russia scored 67 points and placed 11th. Since Russia was among the top 10 countries, excluding the nations that constitute the Big Four, Russia pre-qualified to compete directly in the final of the 2005 Contest.
C1R chose not to broadcast the semi-final of the competition on 12 May 2004 and therefore, Russia was ineligible to participate in the voting. The final was broadcast on Channel One, with commentary by Yuriy Aksyuta and Elena Batinova. The voting spokesperson for Russia was Yana Churikova.