The game's story sees players taking on the role of Rufus, an inhabitant of the junk planet Deponia, as he attempts to seek a new life on the floating city known as Elysium.

The game's story takes place on the planet of Deponia - a world which originally was inhabited by a large human population, until the majority ascended towards living in a utopia-styled floating city called Elysium.

Seeking to follow in his father's footsteps, Rufus, a young man living in the town of Kuvaq, constructs a makeshift rocket in his latest attempt to travel to Elysium.

After a mishap causes the rocket to break up in mid-flight, Rufus manages to land on a cruiser run by the Organon - a militant organisation that terrorises the inhabitants of Deponia and regularly dumps trash on its surface with their craft.

While aboard, he witnesses the Organon, led by Baliff Argus, pursue a young Elysium woman named Goal, who is shocked that they have been covering up the fact that Deponia is still inhabited by humans.

When she awakens, Goal is found to be unable to speak properly as a result of her brain implant - a cartridge based system which stores an Elsyian's memory, that was damaged in the fall - though Rufus learns that her fiancé, Cletus, will reward him handsomely for her return.

After fixing up a garbage mine bike with the help of Doc, a travelling maintenance man, Rufus continues on his journey, and eventually reaches the Lower Ascension Station with Goal.

Seeking to prevent this, Rufus soon finds Goal missing, but follows a trail leading him to trawler vessel owned by Captain Bozo, in which he receives assistance once again from Doc.

[10] However, the majority of critics and gamers liked the game overall, with key points of praise being "A brilliantly absurd story, a fitting comic style and strong speakers."