Last.fm is free, I didn't even think there was a paid version?
I love it, but just to let you know it isn't like spotify or anything. You can't actually choose which songs you listen to and when, it's like your own personal radio station that plays songs similar to artists you tell it you like. For example you'll see things like 'Jason Mraz Radio' which will play a few of his tracks at random along with other similar tracks by similar artists. You can skip tracks you dislike, but can't rewind, skip backwards or replay anything you want at will. You'll see what I mean when you start using it!
That is why it's free, but it's still an amazing way of discovering new music!