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.