《火星大悬案》是《卑鄙的街道》的续集。六年过去，私家侦探特克斯·墨菲破产了，他的运气不好，严重需要一个新案子。他接到了马歇尔·亚历山大（Marshall Alexander）的电话，一个拥有火星上大部分产业的商业大亨。他的女儿亚历克西斯似乎离家出走了，并带走了“别的东西”。马歇尔不说那是什么东西，但他愿意付出巨大的代价来换回它（和他的女儿）。

与前作不同的是，游戏只包含冒险游戏，取消了飞行模拟和动作场面。基本游戏机制与第一部游戏非常相似，将审问和选择置于基于物体的谜题之上。动词命令被用来与环境互动，而审问嫌疑人通常涉及选择对话选项。做出错误的选择有时可能会提前结束游戏或使游戏无法完成。