Nel 29° secolo, la Terra è diventata una landa desolata cosparsa di immondizia a causa del consumismo dilagante e dell'avidità delle aziende; sette secoli prima, la megacorporazione Buy-n-Large (BnL) ha evacuato l'umanità nello spazio su giganteschi Starliner. Di tutti i robot compattatori di rifiuti lasciati da BnL per ripulire, solo un robot rimane operativo, Waste Allocation Load-Lifter: Earth-Class (WALL-E). Un giorno, la routine di WALL-E, comprimere immondizia e raccogliere oggetti interessanti, viene interrotta dall'arrivo di una sonda che trasporta un robot a forma di uovo chiamato Extra Terrestrial Vegetation Evaluator (EVE), che è stato inviato a scansionare il pianeta alla ricerca di segni di vita sostenibile. WALL-E è colpito dall'elegante robot ultraterreno e i due iniziano a comunicare, finché EVE non va in standby quando WALL-E le mostra la sua scoperta più recente; una piantina viva.