Re you using iOS, Android or Windows Phone?
Have you looked in the menu yet? Not all apps are on the home screen.
Try reinstalling the app.
Go to Settings>Apps>Spotify and then hit uninstall.
If you want to reinstall Spotify on Android properly, you may do that by following the steps in the link below.
It's a little bit more than 'just deleting the app'.
http://community.spotify.com/t5/Help-Android/Android-Troubleshooting-Spotify/td-p/113082?nobounce
Go to Settings>Apps>Spotify and then hit uninstall.