AOL said it is investigating a large scale breach of AOL Mail in which "a significant number" of accounts were compromised.
User information including encrypted passwords, encrypted answers to security questions, postal addresses, and address book contacts were compromised, the company said in a blog post.
However, AOL said that no users' financial information has been stolen and there is no indication that the encryption on passwords or answers to security questions was broken.
It remains to be seen if what they really meant to say was that users passwords and questions were hashed rather than encrypted (an important distinction when it comes to securing passwords properly).
As a precautionary measure, AOL advised users of any of its services to change their passwords and security questions.
The company said it is working with an external forensics team and federal investigators to find the source of the "serious criminal activity" behind the compromise, which affected about 2% of AOL Mail accounts.
Some media outlets have estimated that 2% of AOL Mail accounts is equivalent to about 500,000 users.
On 28 April, AOL posted an FAQ on its help page that stated the compromise likely occurred when someone gained access to a portion of the network where user account information was stored.
Our investigation remains ongoing, but we believe that a person gained unauthorized access to the AOL network where some user information is stored.
AOL's announcement confirming the breach on Monday 28 April came after a week of user complaints about spam being sent to their contacts.
On 22 April, the company's mail team announced that it was changing its email authentication policy to crack down on the sending of "spoofed" emails that appear to come from AOL addresses but do not come from AOL mail servers.
Spoofing refers to fraudulently altering an email "From" address header to make it appear as though it came from a stolen email address.
According to media reports, the spam messages appearing to come from spoofed AOL email addresses contain links to malicious phishing websites and online markets for diet pills.
Virus Bulletin reported that malicious links in spoofed AOL emails download a Trojan malware when opened on Android devices.
One spam email obtained by GigaOm contained the subject line "How are you?"
In the message body it simply says "Have you already seen it?" followed by a link to the spam website.
What to do if your account was compromised
If you're an AOL Mail user, visit account.aol.com to change your password and security question immediately.
If you use the same password as your AOL account for other websites, change those passwords as well - and remember, you should use a unique password for each of your online accounts in case one of them is compromised.
Consider using a password manager such as LastPass or 1Password to generate and store complex passwords.
More on password security
For a deeper understanding of password security, listen to this episode of Sophos Techknow - Busting Password Myths.