The song's video took two days to film and ended up running over the allotted time that had been scheduled for production, costing the record label a considerable amount of money.

Yankovic later realized that by releasing "Headline News" on the Permanent Record set rather than wait to include it on his next album, he could capitalize on the topicality of the parody's lyrics.

)[4] Yankovic later joked that he "wanted to write a song about these people because he didn't think they're getting quite enough media attention"—a reference to the stories' over-saturation in the news.

[8][9] Backing Yankovic were Jon "Bermuda" Schwartz on drums, Steve Jay on bass, Jim West on guitar, and Kim Bullard on keyboards.

"[1] The video features several celebrity cameos, including an appearance by Doug Llewelyn of People's Court fame, and long time radio show host Dr. Demento.

[14] The cast also includes Danny Fehsenfeld as Michael Fay, Laura Pursell as Tonya Harding, Maria Causey-Nelson as Nancy Kerrigan, and Sal Rendino as John Bobbitt[15] .

Lou Carlozo of the Chicago Tribune wrote that the song "provided savage laughs at the expense of Tonya Harding and John Bobbitt.

"[21] Roch Parisien of AllMusic cited the song as one of the three stand-outs from Yankovic's second greatest hits volume, and called it a "rib-tickler".

[23] Not all reviews, however, were so positive; an article that appeared in The Commercial Appeal noted that while the video for "Headline News" had some "cute bits and unusual cameos", it was "not as clever as many of Yankovic's past efforts" and that "the current events included here are already dated".

[25] In addition, Yankovic has performed the song with the Crash Test Dummies twice: once on Canada's MuchMusic channel and another time at the House of Blues in Los Angeles.

[26] Reportedly, during one of the performances, Ellen Reid, backing vocalist and keyboardist for the Crash Test Dummies, went out and purchased kazoos.

[11][27] Yankovic's Straight Outta Lynwood concert tour contained new lyrics as part of a parody medley, referencing Britney Spears, dealing with her 2007 head-shaving shock and underpants-less limousine trip in late 2006.