The VA was notified last week that a subcontractor, Unisys Corporation, hired to assist in insurance collections for veterans' medical centers in Philadelphia and Pittsburgh, lost a desktop computer from its offices.
The personal information of about 38,000 veterans is now at risk, according to VA figures.
VA has launched an investigation into the incident, and has dispatched a team to Unisys' offices to assist in the search for the missing PC and to determine what information was on it.
The VA said in a Monday statement that it believes the records affect people who received treatment at the two medical centers in the past four years.
The names, addresses, dates of birth, Social Security numbers, insurance carriers, dates of military service and claims data of people who received treatment at the centers may have been on the computer.
Ron O'Brien, senior security analyst for Sophos, said changing human behavior is integral in preventing many lost or stolen computers.
"When you look at these breaches, human error can only be corrected by changing people's behavior," he said. "We can change things from a technical standpoint, but we can only do so much as far as behavior goes."
Two Maryland men were arrested last week after they allegedly stole a laptop containing the personal details of both veterans and active duty members of the U.S. Armed Forces. The information was never breached, according to a federal investigation.
A VA representative could not be reached for comment, but R. James Nicholson, secretary of Veterans Affairs, promised progress in the investigation via a prepared statement.
"VA is making progress to reform its information technology and cybersecurity procedures, but this report of a missing computer at a subcontractor's secure building underscores the complexity of the work ahead as we establish VA as a leader in data and information security," he said.
Brandon Hoff, chief marketing officer at CipherOptics, said criminals are now aware at the large amounts of money they can make through the sale of personal information.
"All of that can be wroth a lot of money," he said. "We're really seeing people take advantage of the fact that they can make a lot of money with that information."