Addressing a black church in Brooklyn, Bloomberg said he was "sorry" and acknowledged it often led to the detention of blacks and Latinos.
"I can't change history," Bloomberg told the congregation. "However today, I want you to know that I realize back then I was wrong."
Bloomberg's reversal is notable for someone who is often reluctant to admit wrongdoing. It's also a recognition that if he's to compete for the Democratic presidential nomination, he'll have to win support from black voters. And his record on stop-and-frisk is a glaring vulnerability that could hobble his potential candidacy if he doesn't express contrition.
The apology, however, was received skeptically by many prominent activists who noted that it was made as he is taking steps to enter the race.
"It is convenient that Bloomberg suddenly apologizes but has done nothing to undo the immense damage he has caused on countless lives," said activist DeRay Mckesson. "His apology is not accepted."
Stop-and-frisk gave police wide authority to detain people they suspected of committing a crime, and Bloomberg aggressively pursued the tactic when he first took over as mayor in 2002. Under the program, New York City police officers made it a routine practice to stop and search multitudes of mostly black and Hispanic men to see if they were carrying weapons.
Police claimed that people were only targeted if officers had a reasonable suspicion that they were breaking the law. But while the searches did lead to weapons being confiscated, the overwhelming majority of people who were detained and frisked were let go because they hadn't done anything wrong.
Many men found the encounters humiliating and degrading, and statistics showed that minorities were far more likely to be subjected to such a search.
"Under Bloomberg, NYPD increased stop and frisk from 100,000 stops to nearly 700,000 stops per year. 90% of those impacted were people of color - overwhelmingly black and brown men," black activist and data scientist Samuel Sinyangwe tweeted on Sunday. "Bloomberg personally has the money to begin paying reparations for this harm. 'Sorry' isn't enough."
Bloomberg is not the first Democrat aiming to unseat President Donald Trump next year who has sought to atone for past positions on matters that deeply impacted people of color.
Before he entered the race, former Vice President Joe Biden apologized for his role in the passage of a crime bill that imposed stiffer sentences on those convicted of crack cocaine possession - a law that has disproportionately affected the black community. Vermont Sen. Bernie Sanders, too, said he was "not happy" that he voted for the "terrible" 1994 legislation. And Pete Buttigieg apologized for his handling of race as mayor of South Bend, Indiana, a city with a history of segregation where decades of simmering tension erupted this summer when a white police officer shot and killed a black man.
Deval Patrick, the former Massachusetts governor who just entered the Democratic race and was campaigning Sunday in Nevada, was asked for his reaction to Bloomberg's apology. He replied, "Good."
Sen. Cory Booker, who was at the same Nevada rally, had a similarly positive but brief reaction to Bloomberg's reversal on stop and frisk, saying, "I'm happy he did." Julian Castro, the former Housing and Urban Development secretary and presidential candidate, said: "It's interesting timing that the mayor would apologize for that now. That was a wrong policy. I guess it's better late than never. People will have to judge whether they believe his apology."
Rev. Al Sharpton applauded Bloomberg for reversing his stance, though he added that he would have to "wait and see whether it was politically motivated."
"As one who helped lead countless demonstrations, marches and rallies to amplify the racial impact that was had on the Black and Brown community from stop-and-frisk policing, I am glad to see Mr. Bloomberg now admit that the policy was wrong," Sharpton said. "It will take more than one speech for people to forgive and forget a policy that so negatively impacted entire communities."
On Sunday, Bloomberg sought to contextualize his embrace of stop-and-frisk. Though crime had fallen sharply when he took office, he said there were still 650 murders in the city in 2001. Most were young black and Hispanic men. Meanwhile, relations between police and communities of color were at a nadir.
"I was not going to accept that - and I didn't," Bloomberg said. "I was determined to improve police-community relations while at the same time reducing crime even further."
But the practice had unforeseen consequences, he acknowledged.
"The fact is, far too many innocent people were being stopped while we tried to do that. The overwhelming majority of them were black and Latino," he said. "That may have included, I'm sorry to say, some of you here today. Perhaps yourself or your children, or your grandchildren, or your neighbors, or your relatives."
Yet as recent as this year, he defended his handling of it.
"The murder rate in New York City went from 650 a year to 300 a year when I left," he said in January. He said most police departments do the same thing, "they just don't report it or use the terminology."
Ultimately, a federal judge found in 2013 that stop-and-frisk intentionally and systematically violated the civil rights of tens of thousands of people by wrongly targeting black and Hispanic men. Bloomberg blasted the ruling at the time, calling it a "dangerous decision made by a judge who I think does not understand how policing works and what is compliant with the U.S. Constitution."
Bloomberg's successor, Mayor Bill de Blasio made ending the practice a centerpiece of his first run for office. In a campaign-defining ad, his son Dante, who is biracial, made the case that de Blasio "would end the stop-and-frisk era that unfairly targets people of color."
Bloomberg told the congregation Sunday that stop-and-frisk eroded trust in the police department and left a blight on his legacy.
"The erosion of trust bothered me - deeply. And it still bothers me," he said. "And I want to earn it back."
* More New York City news
* Send us a news tip
* Download the abc7NY app for breaking news alerts
* Follow us on YouTube