Basado en la película del mismo nombre, Total Recall te pone al mando de Douglas Quaid, que debe encontrar una forma de llegar a Marte para encontrar las respuestas a sus dos preguntas: por qué le persiguen y quién le persigue. Para ello, Quaid debe atravesar un nivel tras otro golpeando a los malos que se interponen en su camino.
Algunos de los niveles difieren en cuanto a la jugabilidad, y oscilan entre las escenas de acción y las de conducción. Las escenas de acción requieren principalmente que recojas algunos objetos antes de salir del nivel. Sólo tienes una oportunidad para completar el nivel actual, lo que significa que si pierdes la energía, el juego termina. La energía se pierde si te ataca un obstáculo o si te dispara un enemigo. Puedes ganar más energía recogiendo algunas píldoras o un corazón, dependiendo de la plataforma.