Help me out, I genuinely can't think of a music streaming service that came before Spotify.

I vividly remember being blown away by their product when it came to market. I remember because I had never seen anything like it and literally didn't believe it could be done at that time. I was waiting for a train and could just search for any song and play it right away from my phone, no downloading, no waiting, just instant music. I was very sceptical beforehand but was instantly sold.

Did I miss another service that did something even remotely similar before Spotify did it?

Spotify launched in 2008. Rhapsody launched in 2001, then added content from major labels in 2002.

I previously used (and really enjoyed) Rdio, which launched before Spotify came to United States (2010 vs 2011). But Spotify was around before that in Europe.

Pandora radio started in 2000 : https://en.wikipedia.org/wiki/Pandora_Radio

Myspace was a popular way to share music, if limited.

Youtube, again though this doesn't fully fit the definition.

Anybody know about soundcloud? I know I was using that before I heard of spotify but I'm not sure if it came out beforehand.

Pandora wasn't on demand until very recently. It was "station only".

Myspace def. was limited and didn't have full catalogs of all music in any scope approaching Spotify.

Youtube is video that has music, and can't be conveniently used on mobile or used for music discovery explicitly.

Soundcloud is actually the closest to what I meant, but it obviously isn't used for record-label music distribution en masse.

> Youtube is video that has music,

True.

> and can't be conveniently used on mobile

I disagree, but that's highly subjective.

> or used for music discovery explicitly.

It can be, but the YT Music app only was launched in 2015.

Spotify was light years ahead of Pandora when it launched in Europe. I used to VPN through Europe just to use Spotify before it launched in the US. It was a popular work-around for the tech literate in the US circa 2006. People went nuts for the service, though the cachet of it being difficult to access may have helped.