The band wrote the song in under an hour. According to frontman Ian Watkins, it is a song about nostalgia for when the band were growing up together in their home town of Pontypridd, South Wales, and was originally inspired by the Shinobi arcade game they used to play at the Park View Café in Pontypridd. The song's name is derived from the video games Shinobi and Bad Dudes vs. DragonNinja.
"Shinobi vs. Dragon Ninja" was released in the summer of 2001 and became the most successful song from The Fake Sound of Progress on the American rock charts. It appeared on Billboard magazine's Modern Rock Tracks chart at 33. In the United Kingdom the album peaked at 41 on the UK Singles Chart in 2001 and stayed on the charts for two weeks. After the release of the follow-up single "The Fake Sound of Progress" in 2002 "Shinobi vs. Dragon Ninja" re-charted and peaked at 161. The song was featured on the soundtrack of ATV Offroad Fury 2.
The video for this single is one of few Lostprophets videos actually filmed in the UK. It features the band performing to a crowd of people on the roof of a disused multi-storey car park in Edmonton, North London. The video received significant airplay on MTV2. The music video was directed by Mike Piscitelli, who would direct the music video for "The Fake Sound of Progress," the follow-up single to "Shinobi vs. Dragon Ninja." The shooting for the music video started on 5 October on a Friday at an undisclosed location. Any fan that wanted to participate in the music video could simply email their name, age, gender and contact number to the band. Once the email was received, the band chose who they wanted to include in the music video. And alternate version of the music video exists in a completely different setting, this version just shows the band performing in a live setting. This version was also shot in black and white.