Two otherworldly and all-powerful demons are competing with two unwitting human champions over the future of the magical realm of Xanth. One of these unlikely champions is Dug Mundane, a young lad from our world who has just broken up with his girlfriend Pia. His friend Edsel sends him a computer game, betting that if Dug ends up liking it he'll forfeit his attempts to win Pia's heart back. However, when Dug puts the game disk into his computer, he is teleported to Xanth, where his adventures begin.
Companions of Xanth is an adaptation of Piers Anthony's fantasy novel Demons Don't Dream (included in some releases), taking place in his mystical and punny world of Xanth. Unlike Legend's previous parser-based adventures, this one is fully mouse-controlled. Commands such as "take", "give to", "listen", etc. are on the left of the screen; directional icons and an inventory are at the bottom, with an illustration of the current location taking up over half of the screen. The gameplay relies mostly on inventory-based puzzles, with many solutions involving puns.
Besides puzzle-solving, there are also branching conversations with the various characters populating the world. The game is divided into several areas; some are interconnected, while others become unavailable for exploration as the plot advances. It is possible to die in the game, though the player is allowed to undo his last move if that happens. There are also a few instances of getting irrevocably stuck if the player failed to pick up a crucial item in an earlier area. Although the game invites the player to pick up a companion in the beginning, only one choice is correct, while others lead to a premature end of the game. The chosen companion can be talked to most of the time and provides hints and solutions to some puzzles.