In the first act, the player controls John the Baptist from a first-person perspective in the cistern where he has been locked up. Through a game mechanic based on veils, his thoughts are made clear and he can also get a hint of Salome's dance. The second act is the largest one and has an unknown protagonist. The player is able to float over and through the terrace where the dance took place. Much like the aftermath of a battle, all clues of the events are present and left for the player to explore, piece by, piece, using a puzzle mechanic. There are a few characters around, but these cannot be interacted with. Instead, the environment is presented as a living painting where the many aspects of the story are hinted at.
The third act is the least interactive one and requires the player to restart the game. It shows Salome's dance from a distance, with the option to zoom in according to a certain rule. The game is largely controlled through the mouse, along with a number of keys.
The concept of Fatale is more reminiscent to The Graveyard than Tale of Tales' previous project The Path, which takes much longer to complete. Some stylistic effects are inherited however, such as a dramatic zoom view, whispered words in the soundtrack, graphics with grain, and distorted colour effects.