The masks on Travis' wall are from real luchadors.

In the game, Travis' mentor is Thunder Ryu, a former professional wrestler turned Yakuza. Thunder Ryu shares a name with one of the many wrestlers in the game Fire Pro Wrestling, specifically Typhoon Dragon Thunder Ryu, who takes the place of real life wrestler Genichiro Tenryu, due to Fire Pro not having the rights to any actual wrestling federations. It's thought to be either a reference to the Fire Pro Wrestling, or the exact same character, due to the fact the developer, Goichi Suda, got his start in developing games with Super Fire Pro Wrestling 3 Final Bout, and Super Fire Pro Wrestling Special for the Famicom.

The assassin Death Metal's real name is Count Downsend. This is a reference to the heavy metal band "Strapping Young Lad", whose frontman's name is Devin Townsend.

The manager of the store Area 51, Mask de Uh is a reference to the Killer 7 character Mask de Smith.

According to concept art, Destroyman was originally named "Justice".

According to the game's instruction booklet, Dr. Naomi is "hiding a mysterious secret". The secret was later revealed on the official No More Heroes website that Dr. Naomi is 63 and uses cosmetic surgery to upkeep her appearance.

The techniques taught by Randall Lovikov are all based off of the assassins in Suda 51's previous game, Killer 7. For example, Memory of Child lets you dash, a reference to Con Smith and his super speed.

A Nintendo 64 can be seen very easily on a shelf in Travis' apartment during a cutscene after assassinating Dr. Peace.

In the remake, No More Heroes: Heroes' Paradise, the N64 is changed to a SEGA Genesis with a 32X and SEGA CD attachment. This is likely because Nintendo would not want their console to appear in a game on a competitors' platform.