Peu après le départ de Paris en direction d'Istambul, un meurtre est commis. Aux joueurs de retrouver le coupable, le lieu et l'arme du crime mais aussi le moment où il a été perpétré et le mobile. Pour cela, les joueurs disposeront de la durée du voyage, c'est à dire cinq tours. Le vainqueur sera celui qui aura su rassembler le plus d'éléments à l'issue de la partie. Il n'est donc pas nécessaire de tout trouver pour l'emporter ni d'être frustré de se faire griller une découverte par un autre joueur aors qu'on vient aussi de la trouver. Tout est résolu simultanément à la fin. Selon les auteurs, "Mystery Express" nécessitera une approche plus analytique et précise que les autres jeux du genre.

La principale différence avec le "Cluedo", par exemple, est que les indices sont regroupés par paire et non pas représentés par une carte unique. Pour pouvoir éliminer un indice, il faut donc en trouver la paire et, à contrario, découvrir la carte unique pour en faire la solution. L'heure du crime se résoud par un mécanisme spécifique d'observation qui a lieu trois fois durant la partie.

Les différents wagons du train où se déplacent les pions des joueurs permettent de réaliser diverses actions, comme obliger les autres joueurs à révéler une carte d'un certain type ou en subtiliser. Toutes les actions prennent un certain temps, une donnée essentielle du jeu. Voler une carte prend une heure, recevoir des cartes des autres en demande trois. Sachant que chaque étape a une durée donnée, il va falloir faire des choix. En plus, durant le voyage, se déroulent différents événements qui permettent de piquer des cartes.

Chaque personnage dispose d'une capacité spéciale qui permet, pour quatre d'entre eux, d'obtenir des informations complémentaires sur un des éléments à résoudre. Le cinquième personnage obtient plus de temps pour enquêter.

À mi-partie, les joueurs doivent envoyer un télégramme dans lequel il font une hypothèse. Celle-ci servira à départager des joueurs ayant trouvé le même nombre d'éléments de l'enquête. Heureusement, il n'est pas possible que tous les suspects soient coupables. Heureusement que les auteurs n'ont pas prévu cette solution !