In der Zukunft, im Jahr 2131, hat der dritte Weltkrieg den Planeten Erde und dessen Erzeugnisse menschlicher Zivilisation in Schutt und Asche verwandelt. In den Ruinen kämpft immer noch die junge Elite-Soldation Deunan Knute gegen den Feind. Kurze Zeit später wird sie nach Olympus, einer Stadt, in der eine neue Gesellschaft aufgebaut wurde, gebracht. In dieser Stadt sollen Menschen und Bioroids (genetisch verändert Klone, die sich nicht reproduzieren können und keine Emotionen zeigen) friendlich zusammen leben. In Olympus, das von Gaia, dem Hauptkontrollsystem, und dem Rat der sieben Ältesten kontrolliert wird, trifft Deunan Knute ihren alten freund Briareos, der zu einem Cyborg mutiert ist, und lernt die freundliche Hitomi kennen. Durch einen terroristischen Anschlag wird das Lebensverlängerungssystem der Bioroids zerstört. Die Präsidentin Athena von Olympus beschließt, dass das System wiederhergestellt werden soll. Daraufhin wird Deunan Knute damit beauftragt, das Forschungsmaterial "Appleseed" zu finden und es nach Olympus zu bringen. Gegner dieser Mission ist General Uranus, der Anführer des Militärs von Olympus. So versucht General Uranus ein Gelingen der Mission zu verhindern.