More than 250,000 people in Britain have signed up to the service
The music streaming service Spotify has been targeted by hackers.
The Swedish company says people's personal details, including e-mail addresses, dates of birth and addresses, were all stolen.
However, it is thought credit-card details, which were handled by a third party, have remained secure.
Spotify has apologised for the security lapse and advised users who registered on the site before 19 December 2008 to change their passwords.
It is thought hackers gained access to user data at the end of 2008, although the security breach only came to light at the end of last week.
In the dark
Spotify's communications manager, Jim Butcher, told BBC News the company had only become aware of the attack after receiving a message from the hackers.
"We haven't had direct contact, it's all via third-party sources, so we don't know who they are and we don't know where they are from.
"This wasn't some kid playing on a computer, someone has spent hundreds of hours looking to hack into our system."
"We're still trying to find out the reasons they actually hacked our site, so it's difficult for me to say what they want at the present time."
Launched in 2006, Spotify has more than one million registered users.
Instead of receiving a pay-per-download service, users can access the music for free, with tunes interrupted by advertising, or they can pay £10 a month for an ad-free service.
It is thought there are more than 250,000 users registered in the UK, but Spotify stressed that the number of compromised accounts was small.
"We think about 10,000 accounts [could be] at risk, although we are 95% sure it is a fraction of that," said Mr Butcher.
In a blog posting, the company explained how the hack actually took place.
"The information that may have been exposed when our protocols were compromised is the password hashes [codes].
"As stated, we never store passwords, and they have never been sent over the internet unencrypted, but the combination of the bug and the group's reverse-engineering of our encrypted streaming protocol may have given outsiders access to individual hashes."
The company has apologised for the security lapse and promised users that it was making efforts to ensure the hack was not repeated.