Prisoner 849 has escaped from the planet Na Pali (as chronicled in Unreal), but his or her troubles are not over. Picked up by the warship UMS Bodega Bay, the military force the convict to go back to the planet once again, with the mission to recover the data cores of another crashed ship, the Prometheus.
The Return to Na Pali add-on to Unreal features seventeen new single-player missions. Three new weapons are included: the combat assault rifle (a powerful machine gun), as well as dedicated rocket and grenade launchers. The enemies from the original game return, and are supported by a few new ones: Pack Hunters are small dinosaur-like creatures that usually attack in groups. Spinners are small spider-like creatures that spit acid. Finally, there are the UMS Space Marines, who will use some of the same weapons as the player.
As in the original game, the storyline is mostly told through text logs, but in addition, the prisoner records an audio log entry after every mission.
The game comes with six new multiplayer maps and several new game types: Marine Match is a deathmatch against a team of Marines. Gravity Match is standard deathmatch, but with reduced gravity. Terran Weapon Match uses only the add-on's new weapons. Finally, Cloak Match is like a game of Tag, where the player who is "it" is cloaked and has better jump abilities.