"Boss of Me" was released commercially in the United Kingdom, Australia and mainland Europe. Mainland Europe was given a separate release from the British release, which had different cover artwork and a different track listing. The single was marketed as the single from the soundtrack album, Music from Malcolm in the Middle, but the B-sides to all releases were all tracks from They Might Be Giants albums, as opposed to being other tracks from the soundtrack album. "Reprehensible" comes from the band's 1999 internet-only album, Long Tall Weekend. "Mr. Xcitement" went on to be included on their album Mink Car, released two months after the single. "Boss of Me" charted in three countries, reaching number 21 in the UK, 89 in the Netherlands, and saw the band's first appearance on the Australian Singles Chart, reaching number 29.
The "Boss of Me" music video was directed by Ted Crittenden. It is based on Malcolm in the Middle, and contains the characters and set from the show. It begins with Dewey going through a dumpster that says "TMBG Toys". He climbs out of the dumpster, gets on his bike to ride home, with a cardboard box following after him with the "toys" inside it. The box goes into Dewey's backyard where Malcolm is present, the father, Hal, is cooking on a barbecue, and Reese is getting something out of a tree. Dewey opens the box, revealing toy versions of the band. But whenever there's a close-up in the box, it is the real band in miniature. There is now a Hawaiian hula dancer toy in the box, and Dewey sways back and forth with her. Then, Malcolm and Reese begin shooting the toys with paintball guns. The toys fall out of the box onto the ground, as they continue to play the song.