The letter, signed by the attorneys general of 44 states, asks that payment processor CardSystems Solutions - where the breach occurred - "do the responsible thing and notify all affected customers immediately."
The letter also asked the company to reveal the total number of customers impacted by the breach in each state; an explanation of how the breach occurred and how the company is mitigating "consumer injury" caused by the incident; and an outline of its plan to prevent a reoccurrence of a similar breach.
The attorney generals set a deadline of July 25 for a response.
A spokesperson for CardSystems did not immediately return a call for comment.
Last month, MasterCard reported that an intruder had exploited vulnerabilities in CardSystems' network to access cardholder data. Forty million cards of all brands were exposed to potential fraud.
"Consumers have a right to know if their information has been compromised so they can take the appropriate steps to protect themselves," said Washington State Attorney General Rob McKenna, who proposed the letter.
Last week, SC Magazine reported a class-action lawsuit was filed in California on behalf of credit-card holders and merchants against CardSystems Solutions, Visa, and MasterCard after a security breach that exposed 40 million credit cards to potential fraud.