Die Erde war durch den ungehemmten Konsum so zugemüllt worden, dass die Menschheit sie vor siebenhundert Jahren verließ. Zurück blieben Müllroboter des Typs WALL E (Waste Allocation Load Lifter, Earth-Class), die aufräumen sollten, um die Rückkehr der Menschen zu ermöglichen. Jetzt, im Jahr 2805, ist nur noch einer von ihnen funktionsfähig. Unermüdlich sammelt er Schrott, presst ihn zu Würfeln und türmt diese auf. Im Verlauf der Jahrhunderte hat WALL E ein Bewusstsein entwickelt und in dem Container, in den er sich nachts zurückzieht, ein Ersatzteillager angelegt, aus dem er sich bedient, sobald etwas an ihm kaputt ist. Dort steht auch ein Fernsehgerät, über dessen Bildschirm Gene Kellys Verfilmung des Musicals „Hello, Dolly!“ flimmert.

Bis auf eine Kakerlake gibt es eigentlich keine Tiere und Pflanzen mehr auf der Erde. Aber eines Tages stößt WALL E auf eine Pflanzensprosse. Er gräbt sie aus und nimmt sie mit, denn er sammelt Objekte, die sein besonderes Interesse erweckt haben.

Bald darauf erzittert der Boden bei der Landung eines Raumschiffs. Nachdem es den Roboter EVE (Extraterrestrial Vegetation Evaluator) abgesetzt hat, startet es wieder. Die Mission des weiblichen Roboters besteht darin, die Erde nach Leben abzusuchen. Kriterium dafür ist die Photosynthese. Blitzschnell schießt sie, wenn sie sich in Gefahr wähnt. Beinahe hätte sie auch WALL E zerstört. Der verliebt sich in EVE, aber sie achtet kaum auf ihn, bis er sie in seinen Container mitnimmt und ihr seine Schätze zeigt. Als sie dabei die Pflanze registriert, nimmt sie diese in ein Fach ihres Körpers auf und schaltet sich ab. Sie hat ihre Aufgabe erledigt.

Wieder landet ein vollautomatisches Weltraumfahrzeug, um EVE abzuholen. Der verliebte WALL E klammert sich an der Außenwand fest und gelangt auf diese Weise zum riesigen Raumschiff „Axiom“, dem Zufluchtsort der Menschheit. Im Inneren sieht es aus wie auf einem überdimensionalen Kreuzfahrtschiff. Alles ist automatisiert. Die Menschen liegen in Sesseln, mit denen sie zwischen den verschiedenen Stationen hin- und herfahren. Ständig werden sie animiert und über Bildschirme mit Werbung berieselt. Aufgrund der Bewegungsarmut sind sie fettleibig und kaum noch in der Lage, sich aufzurichten. Aber das will ohnehin niemand. Alle haben sich an das bequeme Dasein auf dem Vergnügungsraumschiff angepasst. Individuelle Wünsche oder Gedanken gibt es ebenso wenig wie Politik.

Der Kommandant der „Axiom“ erfährt, dass EVE eine Pflanze mitgebracht hat. Aber bevor er sie begutachten kann, wird EVE vom Bordcomputer OTTO zur technischen Überprüfung geschickt. WALL E sorgt sich um EVE, folgt ihr überall hin – und löst dadurch ein Chaos aus, während der auf Schadstoffe spezialisierte Reinigungsroboter M-O versucht, seine Spuren zu beseitigen. EVE und WALL E verhindern die Zerstörung der Pflanze, aber WALL E wird bei den Kämpfen so schwer beschädigt, dass er nicht mehr funktionsfähig ist.

Während der wie das frei schwebende Steuerrad eines Dampfers aussehende Zentralcomputer alles tut, um die Pflanze zu vernichten, beschäftigt sich der Kommandant mit einer Dokumentation über das frühere Leben auf der Erde und einem Ratgeber zur Wiederbesiedelung. Um eine Rückkehr zur Erde zu verhindern, sperrt OTTO den Kommandanten ein. Das ist offene Meuterei! Schließlich gelingt es jedoch dem Kommandanten, OTTOs Ausschaltknopf zu drücken.

Ein Detektor steuert die „Axiom“ mit einem Hypersprung zum Herkunftsort der Pflanze.

Sobald die „Axiom“ auf der Erde gelandet ist, eilt EVE in den Container mit den Ersatzteilen und repariert WALL E. Aber der Roboter erwacht dadurch nicht aus seinem Stand-by-Modus. Erst als EVE sich ihm liebevoll nähert, springt ein Funke über; er öffnet die Augen und erkennt sie wieder. Die beiden Roboter werden zusammen bleiben.

Mit ihrer Unterstützung beginnen die Menschen mit der Wiederbesiedelung der Erde.