Zed (Jack Black) is a hunter and Oh (Michael Cera) is a gatherer. After being informed that Zed ate from the Tree of Knowledge of Good and Evil, the shaman (Bill Hader) and Marlak (Matthew Willig) banish him from the tribe. After Zed burns down the village by accident, Oh decides to go with Zed on his journey to discover all the world has to offer. Along the way, they encounter Cain and Abel (David Cross and Paul Rudd). Cain kills Abel and informs Zed and Oh that they must escape with him or else be accused of killing Abel.
Afterwards, Zed and Oh find that the girls they want to "lay with", Maya (June Diane Raphael) and Eema (Juno Temple), from their former tribe have been captured and are being sold into slavery. They try to buy the girls' freedom, but Cain ends up selling Zed and Oh. While being taken to a village by the owner with all the other slaves from their tribe, Sodomites attack and take the slaves prisoner, though Zed and Oh escape and hide in the desert, watching the Sodomites.
The next morning, Zed and Oh discover that the Sodomites have left with the slaves. They head off to save the slaves. They come to a mountain and find Abraham (Hank Azaria) about to kill his son Isaac (Christopher Mintz-Plasse). Zed stops them, claiming that the Lord sent him to do so. Abraham takes them to his Hebrew village and tells them about the cities of Sodom and Gomorrah.
Zed and Oh head off for Sodom after Abraham decides to circumcise them. As they arrive in Sodom, they are captured. Cain, now a Sodomite soldier, saves them from being sodomized, calling them "his brothers." The two recalled that they were sold by Cain as slaves and Cain apologizes and offers them food. While being given a tour of the city by Cain, Zed and Oh are offered by Cain to become guards. Shortly after they become guards and are patrolling the city they see the princess Inanna (Olivia Wilde), who is fasting because she feels guilty that most of the city is starving. That night, at a party, Zed is invited by the princess to talk with her.
Inside the palace, Zed sees Maya and Eema serving as slaves, while Oh is forced to follow the very effeminate high priest around the palace. Zed meets Princess Inanna and she asks him to enter the Holy of Holies and tell her what it is like, thinking that Zed is the "Chosen One." Inside the temple, Zed encounters Oh, who is hiding from the high priest (Oliver Platt). There, they get into a heated argument and are then imprisoned for going inside the temple. The two are sentenced to be stoned to death but Zed convinces the Sodomites to have mercy, so they are instead sentenced to hard labor until they die from work. The king then announces that he will be sacrificing his daughter and two virgins (Maya and Eema) as a gift to the gods.
Zed interrupts the ceremony, claiming he is the "Chosen One." A riot starts, Oh saves Eema and Abraham arrives with the Hebrews to overthrow the king. Oh and Eema lay with each other inside the palace, which not only consummates their relationship, but also means that Eema cannot be sacrificed. They then come out to help Zed fight the soldiers (including Cain). The crowd kills all the leaders and proclaim Zed as the Leader being the "Chosen One". Zed turns this down, letting Inanna rule, and instead becomes an explorer with Maya. Oh becomes the leader of the village where the whole adventure started. The two say their goodbyes and head their separate ways.

Question: Why do Zed and Oh travel to Sodom?
Answer: To rescue Maya and Eema.
Alternative answer: save slaves