Mit den Schriftrollen in seinem Besitz beginnt der letzte Ninja mit der Ausbildung eines neuen Ninja-Ordens. Während einer Trainingseinheit wird er auf mysteriöse Weise in das New York des XX. Der böse Shogun ist zurückgekehrt! Der Letzte Ninja wird aus seiner eigenen Zeit gerissen und muss sich wieder einmal mit nichts anderem als dem Glauben an seine eigenen Fähigkeiten verteidigen.
Last Ninja 2: Back with a Vengeance ist ein Action-/Abenteuerspiel, in dem sich der Spieler in der Rolle eines mächtigen Ninjas durch die Gegner kämpfen und dabei die notwendigen Gegenstände sammeln muss. Das Spiel ist in verschiedene Levels unterteilt, von denen jedes einen anderen Schauplatz darstellt und in mehrere Bildschirme unterteilt ist. Die Ansicht ist isometrisch und der Ninja kann sich in vier verschiedenen Dimensionen bewegen (er kann auch rückwärts gehen) und springen.
Feinde, bewaffnet mit Fäusten und verschiedenen Ninjawaffen, wandern durch die Levels. Der Ninja muss sie entweder mit bloßen Händen oder mit den Waffen, die er unterwegs findet, bekämpfen; in beiden Fällen stehen ihm eine Reihe von Schlägen und Angriffen zur Verfügung, und er kann auch blocken. Es gibt eine besondere Waffe, die Shuriken, die in einer geraden Linie geworfen und nicht für den Nahkampf verwendet werden; wenn sie einen Gegner treffen, töten sie ihn sofort oder fügen ihm zumindest schweren Schaden zu.
In den Levels sind Gegenstände wie Schlüssel, Seile, eine Karte oder Hamburger (die die Gesundheit wiederherstellen, wenn man sie isst) verstreut. Um das Spiel zu beenden, musst du diese Gegenstände einsammeln und sie an der richtigen Stelle einsetzen.