This sequel puts you back into the roles of the cavemen, Joe and Mac. This time, a caveman named Gork has stolen the crown belonging to the Chief of Kali Village, and it's up to you to retrieve it by using the 7 Rainbow Stones you will collect on your journey.

Along the way, you will fight dinosaurs, cavemen, and other prehistoric enemies as your travel through the jungle, or through the ice and snow, or even through a volcanic wasteland. Along the way, you can pick up upgrades for your club, or pick up projectiles from eating certain health-recovery items. In some levels, you'll ride in a stone cart, trying to hope over gaps and avoid enemies as you try to reach the end.

The sequel to the first Joe & Mac adds several new features to the predecessor's formula. You can now collect coins in the levels to purchase items from Tiki Village, such as meat to recover your health, or even remodel your hut back at your home village. The game also uses a password system to track your progress. The game also shifts to an overhead map so you can wander to whichever level you wish, and return to completed levels to earn more money or power-ups.