"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 and rides his bike home while dragging the box full of toys. The box goes into Dewey's backyard where Malcolm is raking leaves, their father, Hal, is cooking on a barbecue, and Reese is using hedge clippers on a tree. Dewey opens the box, revealing toy versions of TMBG. But whenever there's a close-up in the box, it is the real band in miniature. A Hawaiian hula dancer toy joins TMBG as Dewey sways back and forth with her. Malcolm and Reese begin shooting the toys with paintball guns until one of them accidentally shoots Hal. Though not shown, it's presumed to have been Reese who shot him as he is later seen using a weed whacker. The John Flansburgh toy is lying in the grass with his arm detached. Reese spots him and, while using the weed whacker, launches him onto the grill where Hal accidentally eats him, much to Dewey's shock. Later, the John Linnell toy is placed in a model airplane that is launched across the street before curving back and landing on the driveway. As Hal drives up, he picks up the airplane to examine it. The plane explodes because it still had a lit fuse. Hal then angrily gathers the TMBG toys into the box and drives back to the dumpster where he promptly tosses it back in.