The mood was somber, with heavy security. Police helicopters flew overhead and police boats patrolled the river.
No one has been arrested in Nemtsov's killing, and Russia's federal investigative agency said it was looking into several possible motives.
Ilya Yashin, a friend and fellow opposition leader, said he hoped the killing would not frighten people.
"Essentially it is an act of terror. It is a political murder aimed at frightening the population, or the part of the population that supported Nemtsov and did not agree with the government," Yashin told The Associated Press. "I hope we won't get scared, that we will continue what Boris was doing."
Russian President Vladimir Putin has marginalized and intimidated his political opponents, jailing some and driving others into exile, since mass anti-Putin protests swept Moscow in 2011 and 2012. Nemtsov, 55, was among the few prominent opposition figures who had refused to be cowed.
Sunday's march could energize the opposition, but it could also prove to be a brief expression of emotions that dissipates in a climate of fear.
Mikhail Kasyanov, a former prime minister who joined the opposition, told the crowd the killing should be a turning point for Russia "for the simple reason that people who before thought that they could quietly sit in their kitchens and simply discuss problems within the family, now will start reconsidering everything that's going on in our country."
Russia's Investigative Committee said it is considering the possibility that Nemtsov's killing was aimed at destabilizing the political situation in Russia and the politician was a "sacrificial victim for those who do not shun any method for achieving their political goals."
This suggestion echoed comments by Putin's spokesman and other Russian politicians that the attack was a "provocation" against the state. The consensus of political commentators on state television was that the killing served the interests of Russia's enemies.
Yashin, however, said Russia's leadership and specifically Putin bore full political responsibility for Nemtsov's death.
"It was President Putin who created this atmosphere of hate in our country, the atmosphere of intolerance, which one way or another materialized in the bullet that killed my friend Boris Nemtsov," Yashin said.
Kremlin propaganda had identified Nemtsov as among the leaders of a "fifth column," painting him and other opposition figures as traitors in the service of a hostile West.
As a former deputy prime minister and longtime politician, Nemtsov retained strong ties among Russia's political and business elite, making his murder additionally shocking.
Sergei Musakov, 22, who took part in the march, said he believed that Putin was responsible for the killing, but thought it would have little impact on the situation in Russia.
"Maybe if 100 people were to die people would rise up, but I don't really believe in that," Musakov said. "People are so under the influence of the (TV) box that they will believe anything that television tells them."
Nemtsov was killed just hours after a radio interview in which he denounced Putin's "mad, aggressive and deadly policy of war against Ukraine." Nemtsov was working on a report presenting evidence that he believed proved that Russian servicemen were fighting with the separatists in Ukraine, despite official denials.
Yashin said it was unlikely the report would ever be published because investigators who searched Nemtsov's apartment after his death took away his laptop.
TV Center, a station controlled by the Moscow city government, broadcast a poor-resolution video from one of its web cameras that it said shows Nemtsov and his female companion shortly before the killing. The station, which superimposed its own time code on the footage, circled figures that it said were Nemtsov and the woman walking across the bridge on a rainy night. A snowplow that moved slowly behind the couple obscured the view of the shooting. TV Center then circled what it said was the suspected killer jumping into a passing car. The authenticity of the video could not be independently confirmed.
Investigators said Sunday that they were again questioning the woman, Ukrainian citizen Anna Duritskaya, who was with Nemtsov when he was killed. LifeNews, a television station with ties to the security services, said Duritskaya told investigators that she was in shock and could not remember what the killer looked like or the car he was in.
The Interior Ministry said it was offering 3 million rubles (nearly $50,000) for information about the killing.
U.S. Secretary of State John Kerry said the United States had no intelligence on who was being the shooting. "The bottom line is we hope there will be a thorough, transparent, real investigation, not just of who actually fired the shots, but who, if anyone, may have ordered or instructed this or been behind this," Kerry said Sunday on ABC's "This Week."
Another mourning march for Nemtsov was held earlier Sunday in St. Petersburg, drawing what police estimated was 6,000 people.
Nelly Prusskaya, a 66-year-old doctor, said she came to pay her respects to Nemtsov.
"I also came to say that I'm against the war in Ukraine," she said. "I'm against political murders."
Most Russians support Putin's policy in Ukraine. Since the annexation of Crimea a year ago, support for Putin has been more than 80 percent.
Irina Titova in St. Petersburg, Russia, contributed to this report.
Copyright 2015 The Associated Press. All rights reserved. This material may not be published, broadcast, rewritten or redistributed.
This post has been updated.