They took responsibility for keeping New York City safe in the aftermath of Sept. 11. And for years, their approach was seen as nearly beyond question, as the threat of terror attacks was kept at bay and the crime rate fell to record lows.

Now, as Mayor Michael Bloomberg and Police Commissioner Raymond Kelly near the end of Bloomberg’s tenure, a backlash against the street stops and surveillance programs they call cornerstones of building “America’s safest big city” has added a tone-changing last chapter to the narrative of policing New York in the past 12 years.

A federal judge this month gave credence to years of complaints that the New York Police Department has stopped millions of people in a racially discriminatory way, ordering a monitor to oversee sizable changes. A City Council that scaled back a 2004 anti-racial profiling law this week voted to make it easier to sue over profiling claims and established a watchdog to investigate police procedures, defying Bloomberg vetoes.

Bloomberg is appealing the court ruling and signaled he will sue to try to block the profiling legislation, but those prospective challenges may not be resolved before he leaves.

Is it a defining episode or a footnote in the administration’s public safety history? That will be up to the next mayor, New Yorkers’ memories and what unfolds in the courts and on the streets, observers say.

“We may have reached an historic point — depending upon what happens,” said William Eimicke, a Columbia University public affairs professor who was a deputy city fire commissioner from 2007 to 2010.

Bloomberg is clear about how he sees his policing record. And he warns that the recent calls to rein in stop and frisk might only prove his policies were right.

“It’s been almost 12 years now where people have walked the streets of New York City without having to look over their shoulder. I suspect that’s a pretty good legacy,” he said after the court decision. Break the NYPD’s embrace of stop and frisk, he admonished successors, and “be responsible for a lot of people dying.”

Terrorism was the top safety concern when Bloomberg took office in January 2002, reappointing Kelly to the commissioner’s job he’d held from 1992 to 1994. They set about sculpting a muscular antiterrorism operation with more than 1,000 officers, some sent overseas to gather information.

Building on a drop in street crime that started under Mayor Rudy Giuliani, Bloomberg and Kelly stepped up the use of statistics to pinpoint crime hotspots and flood them with officers. The mayor became a national voice on gun control. And they upped emphasis on stopping, questioning and sometimes frisking people seen as doing something suspicious but not plainly arrest-worthy: 97,296 stops in 2002 rose to 685,724 in 2011, dropping to 533,042 last year.

There were flares of tension, including over mass arrests of demonstrators during the 2004 Republican National Convention and the 2006 shooting of an unarmed bridegroom on his wedding day.

But overall, the message many New Yorkers heard was one of foiled terror plots and America’s lowest big-city crime rate, as measured by the FBI. Killings repeatedly hit the lowest points on record and are on track for another record low this year.

Kelly has enjoyed the highest approval ratings of any city official.

Still, over the last two years, long-rumbling complaints about stop and frisk became a roar amplified by the mayoral race. The extent of the NYPD’s surveillance of Muslims came to light when The Associated Press detailed tactics that included infiltrating Muslim student groups and putting informants in mosques, disclosures that partly fueled the City Council legislation.

Bloomberg and Kelly went on the offensive, denouncing the practices’ critics and portraying the stakes in ominous terms. “Remember what happened here on 9/11,” Bloomberg chided in one speech.

Some New Yorkers wondered at the officials’ combativeness.

“It’s a shame Kelly’s been so hostile” to the court and council moves, said Karen Lalor, 38, an upper Manhattan home care worker who considers the commissioner generally “a reasonable man.”

It was a fight the powerful mayor and popular police commissioner seemed not to imagine they could lose. But at least for now, they have lost their campaign to stop new checks from being imposed on the NYPD at a time when last impressions can count.

“There’s been a giant shift in the sentiment that was generally very hands-off on policing in New York City and now is very hands-on. … Kelly and Bloomberg came in as crime fighters, and they may be going out as racial profilers,” even if the image is unfair, said Eugene O’Donnell, a John Jay College of Criminal Justice professor.

Besides the courts, the next mayor will shape how the push for NYPD oversight plays out, including by choosing a police commissioner.

Early in the mayoral race, criticisms of Kelly were few. But some candidates now hail plans to rein in stop and frisk and replace him. Others, though, laud him and the policy.

Ultimately, Bloomberg and Kelly’s counterterror and crime rate successes may be what’s remembered, for better or worse, said police history expert Tom Reppetto. Especially if it’s for worse.

“After this administration leaves, the public will say, if there’s a terrorist attack or crime starts to go up … ‘It would never have happened if Kelly were here,’” he said.

Queens resident Eliza Irving feels the Bloomberg administration has focused too much on stop and frisk and given police too much power.

“I don’t feel safer because of his policing policies. In fact, I feel less safe,” said Irving, a 23-year-old high school teacher.

But John Rivera thinks back to being in the city on 9/11. The account manager lives in the suburbs but is concerned for the safety of the city where he works every day, and he still welcomes seeing the NYPD’s added presence when threat levels are raised.

Bloomberg and Kelly “haven’t done the best job,” he said, “but they’ve done a fair job.”

(AP)