IIRC when spotify started it was only available in sweden and was classed as a pseudo-radio which allowed them to get a blanket deal with Swedish Performing Rights Society (STIM) which governs radio/public music license payments for sweden. It also was a case of the record labels being more willing to try this out in a smaller market before committing globally.

I remember using it 2007-2008-ish and it being pretty magical at the time.