Did you know: Spotify uses Ogg Vorbis to stream music

That explains the good sound quality on Spotify. 
Ogg Vorbis is a superior and free audio codec. With ~160kbps (mid quality on Spotify and standard desktop) it has the same quality as 320kbps mp3. If you use the highest quality on Spotify you'll get ~320kbps Ogg Vorbis which is way better than anything possible with mp3.

Even on the lowest ~96kbps setting to save bandwidth on mobile if you like, it's around that quality you'll get out of a 160kbps mp3. Isn't that awesome?

And Ogg Vorbis is a patent free and open source codec around for many years and not challenged at quality for lossy music compression. Yay! 
I'll have to rethink my music subscription and move over to spotify.