Charlie left the band after the release of their debut, self-titled album, and was replaced first by Pete Newbury, with Dave Ehrlich also joining as a second guitarist. Newbury's tenure touring with the band was short-lived, however, he was in turn was replaced with Justin Fisher by the time the band's second album, How To Meet Girls, was recorded and released in 2000. A special EP for My Records, entitled My EP, was released in 2001, and was followed in 2002 by their album, American Cheese.
In April 2003, Nerf Herder appeared as the musical guest in the final-season Buffy episode "Empty Places" – the very last band to play at The Bronze. Their special connection to the series was further acknowledged by a bit of dialogue, with "Rock City News" playing in the background:
After the final American Cheese tour dates - during which time Ben Pringle (now of The Rentals) had replaced Fisher (who had left amicably to front his own band Psoma) - the band had disintegrated, without announcing an official split, by 2003, and a post by Gripp on the band's website some time afterwards detailed how most of the former band members had gone on to get "proper jobs". Gripp, meanwhile, did some work as a jingle writer, which led to his 2005 solo album For Those About To Shop, We Salute You - a 52-track concept album mimicking various musical styles and focusing on product commercialization.
In late 2005, however, Nerf Herder made a surprise comeback, announcing on their website that they were playing a handful of gigs with the original lineup of Parry, Charlie and Steve. For Parry's May 7, 2007 review of the day, he announced that the original lineup had finally finished recording their 4th album and that it did not have a title at this time. Parry stated that he wanted the title to be "Brownerton", but that idea was shot down. Parry also stated that of the 13 songs recorded, they would probably pick 10 to be on the album. In June 2007, the band decided on the title "Nerf Herder IV" with the album released in stores April 29, 2008. Former Size 14 singer Linus Of Hollywood joined the live band (playing guitar and keyboard) in early 2008 for a series of West Coast shows and a short tour of Japan.
The song "High Five Anxiety" is now being featured on the soundtrack for Major League Baseball 2k7 made by 2k Sports.
Mr.Blue Sky was used in the end credits of the Channel 4 Documentary The Great Global Warming Swindle in 2007.