Can't play Spotify via Bluetooth headset

[kraddy]

Whenever I pair my bluetooth headphone (Remax RB - S5 ) with my phone (P9). Spotify doesn't play via the headphone, instead the audio can be heard on the phone speaker. It's quite odd, why there's a need for me to reboot my phone first for me to hear the audio using the headphone. 

Any thoughts?

[ASouthworth]

At the bottom of the play screen (the full one with the album artwork, play/pause button) there should be a devices button. Is that not working?

[kraddy]

The bluetooth headphone is not listed.