WASHINGTON — The Bush administration, in an aggressive new effort to keep illegal immigrants out of the American workforce, yesterday ordered all companies doing business with the federal government to begin ensuring their employees can work here legally.

The order will require thousands of companies to use a government verification system to check the validity of workers’ Social Security numbers. Use of the screening system currently is voluntary for private enterprises but mandatory for government agencies.

The policy initially would apply to new workers but eventually could affect millions of federal contract workers whose jobs range from serving cafeteria food to launching NASA spacecraft. The step is one of several the administration planned after Congress failed last year to pass an overhaul of the nation’s immigration laws.

“The federal government should lead by example and not by exhortation,” said Homeland Security Chief Michael Chertoff, who has been encouraging businesses to use the voluntary “E-Verify” screening system.

E-Verify has been embraced by groups advocating immigration restrictions as a way to weed illegal workers out of the labor force. But it has been criticized by immigration advocates and business groups because of errors within the Social Security database that can lead to false rejections of legal residents and citizens.