Appleseed é um filme que se passa num mundo distópico, onde acabou de ocorrer uma guerra não-nuclear. A guerra durou muito tempo, de forma que ainda existem soldados pelo mundo que não sabem que acabou. Um desses soldados é Deunan Knute, a protagonista do filme.
No início do filme, ela está se defendendo de outros soldados quando um terceiro grupo entra e a captura. Esse grupo pertence a cidade, chamada Olympus que sobreviveu a guerra. A cidade é controlada por um supercomputador, Gaia, regido por sete anciões, The Seven Wisest Men. Metade da população da cidade é Bioroid, um tipo de clone, criados para que a sociedade fique mais estável.
Nesta cidade, a protagonista reencontra um ex-amante chamado Briareos. Antes soldado, ele agora é um ciborgue e por isso Deunan desconfia que ele não é mais a mesma pessoa que ela conhecia.
De acordo com a evolução da trama, a protagonista se envolve entre os personagens Bioroids e humanos extremistas, Briareos entre eles, que querem derrubar o governo.
