The tapes and disks contained personal information and medical records on about 365,000 hospice and home health care patients of the division of Seattle-based Providence Health System .
In a statement, the parent firm said the four workers left the company after "a confidential and thorough internal review process of the data storage procedures that led to the theft."
A Providence Health System spokesman said he couldn't confirm the titles of the workers, but he did note that all four had jobs related to the data-theft incident.
Meanwhile, the health care organization said it has signed an agreement with security vendor Kroll Inc. in New York to provide its ID TheftSmart credit monitoring and restoration services for free to those affected by the theft.
Providence said it will notify affected patients by mail this week about the deal and will provide instructions for signing up for the program.