Debian 8 "Jessie"
Using third-party repositories as recommended below is not supported by the Debian project and could break your system now or when you upgrade later. Use with caution at your own risk!
Add the Spotify repository signing key to be able to verify downloaded packages
sudo apt-key adv --keyserver hkp://pool.sks-keyservers.net --recv-keys BBEBDCB318AD50EC6865090613B00F1FD2C19886
Add the Spotify repository
echo deb http://repository.spotify.com stable non-free | sudo tee /etc/apt/sources.list.d/spotify.list
Update list of available packages
sudo apt-get update
sudo apt-get install spotify-client
Get the latest ligcrypt11 package from sid for your architecture at http://httpredir.debian.org/debian/pool/main/libg/libgcrypt11/ for example
Install libgrypt11 package you downloaded before (be sure to match with your version and architecture)
sudo dpkg -i libgcrypt11_1.5.3-5_amd64.deb