"Song for Shelter" is the first song on the single and the final and longest song on the album Halfway Between the Gutter and the Stars, lasting nearly 11 minutes, with the last two minutes being the track "Talkin' bout My Baby (Reprise)". The song features Roger Sanchez and Roland Clark. A remix for the song by The Chemical Brothers was made and released as a separate single.
The song's vocals are sampled from Roland Clark's song "I Get Deep". The song was featured over the credits on several episodes of Green Wing.
The music video of "Ya Mama" was produced by Traktor, a collective also known for producing Basement Jaxx' "Where's Your Head At?" video and Madonna's music video for "Die Another Day". The song's music video is centered on a tape of the song which makes its listeners unwillingly enter into chaotic uncontrolled arm movements, trembling, dancing, to their own amazement as well as the other persons. Tom and Jerry short Baby Puss can be heard in the background whenever the tape isn't playing. It was filmed in Carriacou in the Grenadines, where a complete town market was built and destroyed.