HCA Inc. said 10 computers containing Medicare and Medicaid billing information and records of employees and physicians were stolen from one of the company's regional offices.
HCA officials won't say where or when the theft occurred because they believe that might help the thieves, who authorities believe were after computer hardware, not personal identity information.
"We don't want to tip them off they may have information that they might use to perpetuate identity theft," said HCA spokesman Jeff Prescott.
The Nashville-based for-profit hospital operator reports on its Web site that the FBI is investigating the incident.
The computers held thousands of files on Medicare and Medicaid patients treated at HCA hospitals in Colorado, Kansas, Louisiana, Mississippi, Oklahoma, Oregon, Texas or Washington state between 1996 and 2006.
The machines contained some patient names and Social Security numbers but no addresses or dates of birth.
Prescott said on Thursday the company had also discovered that the names and Social Security numbers of about 7,000 employees and physicians in four states - Colorado, Kansas, Louisiana and Texas - were on the computers.
He said the company is notifying those affected by letter.
Authorities believe the computers were stolen by a gang that has committed numerous break-ins in the same area, looking for computers to be sold for their hardware and not the data, according to HCA.
HCA has posted notices about the theft on hospital Web sites and in newspapers and will provide credit counseling to concerned patients.
HCA has created a call center, reached toll free at (800) 354-1036, to help affected patients with their concerns about the stolen computers.
HCA owns or operates 176 hospitals, 92 freestanding surgery centers and facilities for outpatient and ancillary services in 21 states, England and Switzerland.