Treize ans se sont écoulés entre la naissance du projet dans la tête d'Andrew Stanton et la sortie en salle. En 1995, Stanton a l'idée de l'histoire du film, mais juge qu'un film sur un robot muet n'aura aucun budget. Lors du projet
Le Monde de Nemo, l'écriture de
WALL-E reprend.
L'idée lui vient lors d'une comédie musicale. Il se demandait ce qui arriverait si ce que laissait l'homme sur Terre de plus humain était une machine. C'est pourquoi notre petit robot danse sur du Gene Kelly et que la chanson d'ouverture du film,
Put On Your Sunday Clothes, provient de la comédie musicale.
Au départ, la seule idée était un robot laissé sur Terre.
EVE et l'histoire d'amour viendront plus tard. Si
WALL-E était déjà en tête mentalement et graphiquement depuis des années,
EVE demanda plus de travail, à savoir neuf versions pour en arriver à la forme actuelle.
Pour les humains, ils évoluèrent beaucoup sur le design. A la base, ce devait être des personnages verts et gélatineux. A ce niveau là, aurait eu lieu une rébellion des robots face à ces "gélatineux". Le titre était alors
Trash Planet. Petit à petit, les artistes ont fait évoluer le design et se sont rapprochés de la version "humaine", avec les conseils d'un expert de la NASA sur les atrophies dues aux voyages dans l'espace, et l'histoire est devenue celle du film.
Le concepteur des bruitages de
WALL-E n'est autre que Ben Burtt, l'ingénieur du son de
Star Wars.