The company didn't explain why it believed a breach to have occurred but the tone of apologetic urgency was unmistakable.
"We are currently investigating the leak of some Last.fm user passwords. This follows recent password leaks on other sites, as well as information posted online," said a notice on Last FM's site posted late on 7 June.
"We will never email you a direct link to update your settings or ask for your password," continued the notice after asking users to change their password as soon as possible.
Security companies have reported that the number of Last FM passwords stolen could be as high as 2.5 million.
Perhaps there is strength in numbers as far as embarrassment goes, but the latest breach is starting to look like part of a pattern.
"Can it be coincidence? It seems unlikely to me. There's a mystery in the middle of the about how they got the data. You have to worry there's a common vulnerability," resident Sophos security expert Graham Cluley told the BBC.
"The fact is, the only people who know are the hackers and maybe the companies concerned, but they may be struggling to work out what's happened.
Two other sites also appear to have suffered major password breaches in recent days, LinkedIn and dating site eHarmony - the second to hit the latter site in recent times. If a specific vulnerability connects these hacks to one another more breaches will probably follow in the coming days.
Gaining access to passwords does not immediately reveal them as long as they have been 'hashed' - encrypted - but even this technique might no longer be sufficient to deter determined attackers if 'salting (the addition of random elements that makes hash comparison against a lookup table nearly impossible).
"The indiscriminate proliferation of data breaches across all industry sectors should serve as a clear warning that perimeter defences such as encryption and anti-virus software, are no longer enough to effectively protect IT infrastructures and personal information," said Ross Brewer of LogRythm.