Before the game begins, players arranged the interlocking room and corridor tiles on the playing area to represent a maze (a "Space Hulk"). Alien Artefact counters are randomly placed throughout the play area. Each player sets up their 5 models in a starting room of their choice and then take turns to move their pieces. The object of the game is to move the various Scout models to retrieve the artefacts and carry them to the starting rooms while stopping opponent models from achieving the same goal. Random event cards are dealt to each player that allows them to either help their own models (in the form of medipacks or double movement) or hinder opponents (by placing obstacles in their path or attacking them directly).
Unlike other Games Workshop games, Ultra Marines featured a unique method of determining the accuracy of weapons fire and close combat attacks. The box of the game featured a grid printed on the inside of the lid, and dice were thrown into the lid and the results read from the squares that the dice landed in. However, this led to eventual problems after release as the cardboard box would warp or become worn after years of use and the distortion of the box lid would skew results.