Shortly after Avidan joined Game Grumps in June 2013, fan speculation and leaks hinted at Avidan working on a new music project with Wecht and Hanson. Fans also discovered earlier hints about the band before Dan joined, as well. Avidan stated during his guest appearance on the July 12, 2013 stream of Polaris video gaming show Friendzone! that he was thinking of names for a new music project he was starting with Wecht.
Starbomb was, eventually, unveiled on December 2, 2013, with a minute-long snippet of "I Choose You to Die" being released on Ninja Sex Party's official YouTube channel on the same day, with the announcement that their debut album would be released in two weeks on December 17, 2013. The album was promoted further with an additional two more snippets, "Mega Marital Problems" and "Crasher-Vania," released on December 10, 2013; a fourth and final snippet from Starbomb, "Sonic's Best Pal," was released on the eve of the album's release on December 16, 2013. In further promotion of Starbomb, Starbomb T-shirts, official posters and stickers were made available to purchase on Rodeo Arcade, with versions of the album available to purchase with the merchandise as well when the album was released.
A music video for "Luigi's Ballad" was released on December 17, 2013 and was directed and animated by Hanson, with additional animation by Studio Yotta. Another animated music video was later released for the song "Rap Battle: Ryu vs. Ken" which was animated by Spazkidin3D. On April 8, 2014 another animated music video, for "It's Dangerous to Go Alone," was released on Egoraptor's channel, directed by Joel C and animated by Studio Yotta. A lyric video for the song "Regretroid" was released on March 11, 2014, with typography by Octopimp, and a "rap-along" version of the song "I Choose You To Die" was released on March 25, 2014. This version featured famous YouTube personalities rapping along to different parts of the song. It included Rocco Botte, Ashly Burch, Keith Apicary, James Rolfe, Markiplier, Dude Huge, The Completionist, ProJared, Steve Kardynal, Chloe Dykstra, and Smooth McGroove.
Many people had shipping issues with the CD version of Starbomb, so a video was put up on Hanson's channel on May 20, 2014 as an apology, and to make up for it, a free Starbomb pin was going to be shipped to anyone who ordered the album before May 23, 2014. This gave people a chance to order the CD before the 23rd so they could get this limited edition pin. The pins were shipped July 7, 2014.