In the world’s most diverse city, it was hailed as a milestone: Mayor Michael R. Bloomberg signed an executive order in July 2008 requiring every New York City agency that dealt with the public to provide interpreters, translated documents and other language help to people who spoke little or no English.

The order was supposed to help immigrant New Yorkers use services and navigate a daunting city bureaucracy. And in keeping with Mr. Bloomberg’s passion for applying good business practices to city government, the policy was meant to prevent the waste of time and money caused by miscommunication and misunderstanding.

Mr. Bloomberg pledged at the time to “make our city more accessible, while helping us become the most inclusive municipal government in the nation.”

But two years later, the mayor’s promise has fallen short. Many government workers fail to offer interpreters, even if people ask for them, and signs and forms in multiple languages are often nowhere to be found, according to people who have sought services and a lawsuit filed against one of the city’s largest agencies where the problems seem particularly acute.

The agency, the Human Resources Administration, is a virtual lifeline to millions of New Yorkers who depend on it for benefits like food stamps, cash assistance and subsidized medical care.

Uk Do Lee, 81, a retired inventor from South Korea, said he had been trying since April to apply for subsidized medical coverage for low-income older people. The first thing he told a caseworker at one of the agency’s offices in Elmhurst, Queens, was, “Korean — no can speak English,” he recalled in an interview.

Mr. Lee asked for an interpreter, to no avail. He said that because he did not understand what the workers were saying, he had to return to the office repeatedly to hand in documents he filled out with outside help, only to understand from them vaguely that another piece of information or another form was required. Mr. Lee said he had requested an interpreter every time, but they insisted on dealing with him in English.

“The workers don’t listen,” Mr. Lee, who lives in College Point, Queens, said through an interpreter. “They regard themselves as kings.”

Across the city, immigrants and the advocates who help them shared similar experiences. Zoila Almonte, 59, an unemployed janitor from the Dominican Republic who lives in Washington Heights, said workers at a food stamp office on West 218th Street often recruited people in the waiting room as interpreters. “I only get Spanish-speaking caseworkers by chance,” she said.

A lawyer who works at South Brooklyn Legal Services said Spanish speakers were routinely told that they had to come up with their own interpreters at a New York City Housing Authority office in Brooklyn that processes subsidized housing vouchers.

And a study based on interviews with 817 immigrant New Yorkers to be released on Wednesday describes complaints about a lack of interpreters in dealings with the Human Resources Administration, the Police Department and Department of Housing Preservation and Development, which oversees the city’s affordable housing programs.

The study, by two advocacy groups, Make the Road New York and the New York Immigration Coalition, found that many immigrants had no idea they were entitled to interpreters and translated forms, in large part because city workers had never told them and they had found no signs explaining their rights.

Robert Doar, commissioner of the Human Resources Administration, acknowledged shortcomings but said that language access was a priority. The agency, he said, “assists more than 3.5 million people each year on a wide range of benefits, and when there are specific complaints, we diligently investigate them and take appropriate action.”

Even before Mr. Bloomberg issued his order, however, the agency’s poor record of providing translation and interpretation prompted the City Council to approve legislation seven years ago dictating the types of language help it should offer to guarantee immigrants’ equal access to benefits. Legal Services NYC, a legal aid group, sued the agency in August, claiming that its failure to comply with the law had “deprived individuals of the necessities of life and repeatedly subjected them to humiliating discrimination.”

Amy S. Taylor, the lawyer who filed the suit on behalf of 12 plaintiffs, said, “There’s a stark divide between what the agencies have on paper and what happens on the front lines.” The suit has not yet gone to trial.

The mayor’s executive order required 37 city offices and agencies to develop plans on language services and to train workers to ensure that the services were made available. No extra money was set aside, so many agencies, like the Department of Aging, recruited multilingual volunteers among their staff members.

The mayor’s office says it ensures compliance through visits to field offices and a sort of secret shopper program in which undercover inspectors look for multilingual signs and translated documents, among other things. City officials said the inspectors’ findings would be released this year.

“We are providing the tools necessary to implement the language-access plans, while holding agencies accountable for their service delivery,” said Elizabeth Weinstein, the city’s director of agency services.

According to Ms. Weinstein, 84 percent of the agencies have started to train staff members on what Mr. Bloomberg’s order requires. More than 7,700 frontline workers and supervisors at the Human Resources Administration, about half of the agency’s work force, have been trained so far this year and will be retrained before the year ends, Mr. Doar said. The agency also has an office that ensures that language services are available and it runs regular compliance checks, he said.

Advocates for immigrants agree that progress has been made and cite as a success the city’s 311 help line, which connects callers to interpreters in more than 100 languages. But they say the message is still being lost as it trickles down the chain of command.

“Part of the challenge is that it takes repeated training, and it takes funding to make this become second nature to front-desk government workers,” said Chung-Wha Hong, executive director of the New York Immigration Coalition. Each missed opportunity to make the right connections, she added, “can lead to major consequences for the individual who is trying to make it through the system.”

Mercedes Cruz, 47, an immigrant from Honduras who lives with her three children in Sheepshead Bay, Brooklyn, is one of the plaintiffs in the lawsuit against the Human Resources Administration.

She first applied for food stamps and cash assistance in 2007 at an agency office in Coney Island, and in her 20 or more visits there over two years, she said, she was never offered an interpreter — not even after her lawyer wrote a letter saying that the agency was required to provide one. She ultimately received benefits, but only after a wait of several months and absences from school by her oldest son, a sophomore at Brooklyn College, who translated for her.

“It shouldn’t be so difficult to get the help I need and qualify for,” she said.

Zena Kim oversees a small team of lawyers at the MinKwon Center for Community Action, a Flushing, Queens-based community group that is another plaintiff. She has to devote considerable time helping older, unemployed Korean immigrants fill out application forms for public benefits because, Ms. Kim said, so many of them refuse to go to the Human Resources Agency alone.

“They find the process very daunting — that they have to speak English and do an interview in English,” she said.

Linda Lee, an outreach coordinator at MinKwon who handles health and labor issues and organizes workshops, does the same for Chinese speakers and sometimes accompanies them to the agency’s offices to turn in applications and make sure all requirements have been satisfied. “We’re doing the full intake just like a social worker will do if we were at an H.R.A. office,” Ms. Lee said. “The thing is, that’s not our job. That’s the city’s job. The mayor himself said so.”