Najważniejsze w przygodówkach, typu point&click jest fabuła. Ta na samym początku przedstawia się dosyć groteskowo i niewinnie, by w połowie odkryć swoje prawdziwe oblicze. A więc cała akcja dzieje się na tytułowej Deponii, to planeta, jak wynika z grania i poznawania świata, która bardzo dawno temu przeżyła apokalipsę, a wszelkie skrawki ziemi zostały zasłonięte przez ogromne stosy śmieci. Innymi słowy bród, smród, ubóstwo, ten kto ma czystą wodę, jest bogaty. Po wpadającej w ucho piosence Huzza, który dośpiewuje co rozdział nowy akt przygody, poznajemy naszego głównego bohatera gry - Rufusa. Rufus to ignorant, cham,nieprawdopodobny leniuch i źródło wszelkiego chaosu spowodowanego w mieście Kuvaq, w którym spędzimy dużą część gry. Dowodem tego są jego wstawki, dość upokarzające tych, z którymi rozmawia i jego patrzenie na świat. Po mieszkaniu z swoją byłą dziewczyną Toni, która ma już dość tego, że Rufus jest takim samolubem i nie pomaga w domu (zmywanie naczyń, pójście do pracy, przynoszenie kolejnych śmieci do domu, nie zrobi sobie sam jedzenia, bo paluszki by sobie pobrudził itp.) Rufus postanawia wnieść w życie kolejny plan ucieczki z Deponii. Otóż chce on dostać się do Elyzjum, jest to latające miasto które znajduje się na orbicie planety. Elyzjum słynie z bardzo rozwiniętej technologii, innego lepszego standardu życia jest cywilizowanym miastem. Uważa on, że nie pasuje do tego miejsca (inni też tak sądzą, i chcą się go szybko pozbyć) i wymyśla różne absurdalne plany, które zawsze kończymy się wybuchem danej maszyny, uszkodzeniami ciała, czy uprzykrzenie innym spokojnego życia. Tym razem, poprzez wystrzelenie się z rakety, do której będzie przymocowana metalowa komora, chce wybić się do specjalnego krążownika, który zabierze go do Elyzjum. Jak potoczą się jego losy? Kogo spotka na krążowniku? W jakie tarapaty wpadnie Rufus (a wpadnie w bardzo duże)?