Au début du xxiie siècle, la compagnie Buy-N-Large (BnL) monopolise l'économie de la Terre par un trust concentrant les biens et les services. Cette entreprise est devenue un gouvernement mondial globalisé. La surconsommation effrénée a tôt fait de transformer le monde en un dépotoir gigantesque. La société commandite un exode massif à bord de vaisseaux spatiaux dans une tentative de préserver l'Humanité. Des milliers de machines robotiques dénommées WALL-E (Waste Allocation Load Lifter: Earth-Class - littéralement en français « compacteur terrien de déchets ») ont été fabriquées par la compagnie. Ces engins ont pour unique tache de « nettoyer » la Terre en compactant la myriade de détritus qui parsèment le sol, durant les cinq années que doit durer l'exode. Mais beaucoup d'entre eux se désactivent inexplicablement et sont hors-service, forçant les humains qui n'ont pas d'autre plan de repli à rester dans l'espace.
Sept cents ans après le début de l'exode humain, il ne reste plus qu'un unique WALL-E en état de fonctionnement. Il fonctionne à l’énergie solaire et déploie au matin des panneaux photovoltaïques pour recharger ses batteries. Ce robot est toujours concentré sur sa tâche quotidienne ingrate, sans variations, sans distractions.
Au fil du temps, il a acquis une personnalité et une conscience propres. Il conserve divers objets ramassés pour leurs utilités mécaniques, esthétiques ou fonctionnelles. Il les trie dans son lieu de repos, engorgé de beaucoup de ses trouvailles. Pour perdurer depuis si longtemps dans sa mission, le robot possède tout un stock de pièces détachées et il remplace ses parties mobiles usées par celles que d'autres WALL-E devenus inertes conservaient sur eux. Par exemple, ses chenilles, sa carte électronique ou ses yeux sont remplaçables. Il nourrit et protège un cafard, nommé HalNote 1, qu'il a rencontré. Il trouve même un jour une plante verte. Il l'arrose et la conserve dans son abri.
Une fusée va détruire la solitude et les habitudes de WALL-E en déposant une sonde robotisée juste devant lui, un matin. Elle est immatriculée EVE (Extraterrestrial Vegetation Evaluator, littéralement Évaluatrice de la végétation extraterrestre). Sa mission est de ramener aux humains une preuve de vie sur Terre. Le robot nouvellement arrivé est tout à l'opposé de WALL-E (qui est un cube basique, rouillé, abîmé par le travail, avec de simples chenilles pour se déplacer). EVE est nettement plus évoluée. Son apparence est fuselée, oblongue, élégante. Elle ne se déplace que dans les airs, très vivement. Elle possède en outre un bras-fusil qui tire des rayons lasers particulièrement destructeurs.
WALL-E apprécie infiniment la distraction qu'EVE lui fait ressentir, hors de sa routine si coutumière. Dès lors, il oublie tout de sa propre mission de compacteur. Il la suit continuellement, scrute ses mouvements, ses déplacements et ses actions. Il cherche comme il peut à communiquer avec elle. Toute à sa tâche, elle le dédaigne pourtant longtemps. Après être parvenu à nouer contact, il lui montre son lieu de repos. C'est une sorte de conteneur auparavant fonctionnel pour recharger tous les WALL-E durant la nuit.
Vivant maintenant seul dans les lieux, WALL-E y a entassé ses nombreux trésors chinés lors de son travail. Il a notamment une télévision fait à la main avec les deux chansons, Put On Your Sunday Clothes et It Only Takes a Moment, du film Hello, Dolly! en vidéo-cassette. Lui présentant ses affaires hétéroclites, il s'émerveille qu'elle puisse créer de la lumière avec des ampoules non branchées ou compléter un Rubik's Cube. Il lui offre la plante trouvée lors de ses opérations de nettoyage sans savoir que c'est ce qu'elle recherche.
Puisqu'elle est une preuve que la vie est à nouveau possible sur Terre, le rôle d'EVE est accompli sur la planète : elle se met donc en stase et reste inerte dans le conteneur. Une lumière verte se met à clignoter à intervalles réguliers sur une partie de son fuselage, indiquant qu'elle a réussi sa mission.
Infatigablement, durant une longue période, WALL-E cherche à s'assurer qu'elle puisse redevenir mobile. Prenant exemple sur sa propre composition, il présume qu'elle manque d’énergie et une grande partie de ses activités consiste à utiliser diverses techniques pour interagir avec elle et la faire redevenir active. Toutes sont infructueuses. Il n'a en fait pas encore compris pourquoi elle est devenue immobile.
Puis, comprenant finalement qu'elle ne peut pas être « réparée », WALL-E reprend son activité principale. Il a cependant si peu d'entrain qu'il plonge dans une sorte de mélancolie profonde.
Entre-temps, la fusée qui a déposé EVE revient la chercher. WALL-E accourt pour ne pas la laisser partir sans lui. L'appareil embarque EVE dans la soute puis décolle. Il emmène aussi WALL-E qui a utilisé ses pinces pour s'accrocher à la coque extérieure de l'engin.
La fusée emmène EVE, toujours en léthargie depuis qu'elle a la plante, et WALL-E (en passager clandestin), à un énorme vaisseau spatial nommé Axiom, abrité dans une lointaine nébuleuse. Ce qu'il reste de l'Humanité mène ici une vie assistée en permanence par la technologie. Du fait de leur complète passivité et dépendance envers les machines, les humains ont perdu l'usage de leurs jambes atrophiées, sont ventripotents et ne se déplacent désormais que sur des fauteuils volants. Leur oisiveté les a rendu incapables de s'extraire de la technologie. Leur libre-arbitre est même devenu inexistant. Le capitaine du vaisseau, B. McCrea, a lui aussi laissé le contrôle de ce dernier à AUTO, le pilote automatique (comme d'ailleurs ses prédécesseurs avant lui).
Lorsque les cinq sondes EVE envoyées sur Terre sont scrutées par le robot GO-4Note 2, qui est le Second du Commandant, seule l'EVE ayant été en contact avec WALL-E contient une plante. Dès lors, un protocole standard est mis en pratique et l'EVE en stase est directement emmenée vers la salle de commandement. WALL-E s'empresse de la rejoindre. Il parvient à se cacher près d'elle.
WALL-E reste caché. EVE est réveillée et salue le capitaine humain. Ce dernier apprend qu'une trace de vie organique terrestre, si elle est placée dans le holo-détecteur, obligera automatiquement le vaisseau à revenir sur la planète Terre. Les humains pourront alors immédiatement la recoloniser. Cependant, AUTO a secrètement ordonné à son assistant GO-4 de voler la plante avant d'aller parler avec le capitaine. EVE est donc considérée comme défectueuse puisque la plante n'est plus apparente en elle. Elle est envoyée au nettoyage avec d'autres robots, et cela ne lui plaît guère. WALL-E salue lui aussi l'humain avant de suivre EVE, et ce faisant laisse un peu de débris organiques sur sa main.
En cherchant à déterminer ce dont il s'agit, le capitaine est surpris de découvrir qu'il s'agisse d'une matière provenant de la Terre. Il se passionne vite pour les descriptions scientifiques qui découlent de sa découverte, ce qui sous-entend que les connaissances biologiques de base ne sont même plus enseignées aux habitants de l'Axiom.
WALL-E croit par erreur qu'EVE se fait torturer lorsqu'ils se trouvent dans la salle de nettoyage. Il provoque la pagaille et l'évasion des autres robots en réparation. Il suit l'évaluatrice de vie qui le guide dans le vaisseau. Ils arrivent ensemble dans une salle où EVE sait que les soutes permettent de s'extraire du vaisseau pour retourner sur la Terre. Elle souhaite que WALL-E y prenne place pour être évacué du vaisseau-mère où il n'a pas de mission à réaliser. Tandis que le robot cubique ne souhaite pas du tout retrouver la solitude et cherche à s'éloigner des capsules, GO-4 arrive silencieusement et place la plante, qu'il avait subtilisée à EVE, dans une capsule de secours qu'il veut faire exploser dans l'espace. WALL-E y entre rapidement à l'insu du Second du Commandant. Il parvient à s'échapper à temps en se propulsant dans l'espace grâce à un extincteur, gardant la plante dans son compartiment de compression. Il retrouve EVE à l'extérieur du vaisseau et se réconcilie avec elle.
Ils retournent ensuite voir le capitaine et veulent lui donner la plante. L'opération est alors enclenchée. Désormais, puisqu'une plante a été déclarée découverte, il est devenu possible pour les humains de retourner sur Terre. AUTO, pourtant, interdit cette possibilité car il obéit au vieil ordre donné par le patron de BnL, Shelby Forthright, donné sept cents ans plus tôt, croyant, à l’époque, que le fait de l'augmentation de toxicité a rendu la vie sur Terre impossible (expliquant pourquoi les autres WALL-E se sont désactivés).
S'ensuit alors une mutinerie : le capitaine est enfermé dans ses quartiers, EVE est désactivée, WALL-E court-circuité par AUTO, et les deux mécaniques sont éjectées dans un conduit d'évacuation des déchets. WALL-E et EVE sont sauvés de justesse par un petit robot nettoyeur nommé M-O (Microbe-Obliterator, littéralement Microbe-oblitératrice, qui n’arrêtait même pas de poursuivre et nettoyer WALL-E depuis son arrivée dans l'Axiom), qui leur permet de regagner l'intérieur du vaisseau. Pourchassés comme renégats, EVE, WALL-E et M-O, aidés de plusieurs robots hors-système cherchent toujours à apporter la plante au commandant : celui-ci parvient à leur faire savoir qu'il va activer le holo-détecteur près de la piscine centrale du navire. Tous les robots se dirigent alors vers le holo-détecteur, tandis que le capitaine fait croire à AUTO qu'il a la plante dans ses propres mains. Lorsque l'appareil trouve le capitaine dans la salle, ils se battent, et GO-4 est détruit dans la manœuvre.
Le capitaine parvient presque à activer le processus qui lui permet de retourner sur Terre, mais AUTO devient finalement fou et fait tomber le capitaine qui s'accroche à lui, bascule le vaisseau (mettant la vie des passagers en danger) et annule l'activation. WALL-E empêche AUTO de fermer la machine, s'endommageant de plus en plus en résistant. Inspiré par le sacrifice de WALL-E, le capitaine décide (contrairement aux passagers et leurs ancêtres, enfin, après toutes ces années) de se lever par lui-même pour affronter AUTO, puis le désactive à temps, remet le vaisseau à l’endroit et sauve les passagers. La plante est mise à temps dans le holo-détecteur avant qu’il se ferme pour toujours, puis l'Axiom prend la direction de la Terre, mais sans trop de joie pour les humains, robots, et surtout EVE. En effet, WALL-E se perd.
De retour sur la planète, WALL-E est réparé par EVE mais malheureusement, sa mémoire a été effacée après sa réactivation. EVE lui donne un baiser d'au revoir qui va lui rendre sa mémoire. Pendant que les deux robots savourent leur nouvelle vie de couple avec leurs autres amis robots, les humains, qui ont retrouvé la marche bipède, reprennent le cours de leur histoire après les sept cents ans de stagnation passés sur l’Axiom, et recolonisent la Terre.