Unlike most of the Lemmings games, Paintball is not a side-scrolling puzzle game where lemmings are constantly on the move and need giving commands to control; instead the gameplay is an isometric tactical shooter where lemmings are controlled directly and don't move unless told to. While the main objective is still to get to an exit in the level (this time marked by a flag), the core of the gameplay consists of splattering enemy lemmings with a paintball gun. Levels may involve up to four player-controlled lemmings; if there are four flags on the level, all four lemmings must survive to reach a flag each. The levels contain various puzzles including moving platforms, lemming catapults, trampolines, and switches and keys that open gates; ammo is limited and can be restocked by picking up paint blobs.

A Next Generation critic commented, "Like most Lemmings games, the sound and graphics are cute and simple, but not stunning, and gameplay is entertaining. The biggest problem is ... when dealing with squares on the other side of raised areas, there's no way to tell if it's dangerous or safe, except by sacrificing a lemming to find out."^[2] GameSpot reviewer Tim Soete praised the game's strategy, networked multiplayer, soundtrack, inclusion of two older Lemmings games as a bonus, graphics, and challenge, while criticizing the frustratingly difficult terrain.^[1] GameRanking's scores list it as 63%, based upon three reviews.^{[citation needed]}

• Web archive of Psygnosis's official Lemmings Paintball webpage
• Lemmings Paintball game review at GameSpot
• Lemmings Paintball at MobyGames