Puzzle Quest features an epic story, based in the Warlords game universe. Players assume the role of a character with various statistics such as combat ability, morale, and magical affinity. A character's predisposition toward individual attributes and spells is determined by the selection of one of four professions at the start of the game. During play, the player takes on quests as part of the main storyline, as well as accepting side quests in order to gain items, experience and gold. Gold can be used to buy equipment that offers bonuses in combat, or it can be used to build up a citadel that unlocks additional content and customization for the character.
The game uses a simple map with new points of interest appearing as the game proceeds. Each new location is connected to one or more existing locations, and hence one often needs to travel through several intermediate points in order to reach a desired location. Foes periodically appear on the links between locations, blocking movement until they are defeated. Key quest locations are also marked on the map, and completing quests typically involves visiting such locations in order to defeat one or more opponents in one-on-one battles.