The steamboat first appeared in the prologue of Mafia: The City of Lost Heaven. Later, it appeared in the mission Happy Birthday when ordered by Don Salieri, Tommy Angelo murdered the City Councilor during his speech on his birthday party held aboard the boat. This was also the last in-game appearance of the ship.
The Lost Heaven Queen has three decks, the first one mainly being ship personnel and work area, the second is the restaurant deck with an outdoor dining terrace as well as an indoor salon complete with a bar. Most cabins are also located on the second deck. The third deck houses the first-class cabins, as well as a stage for musicians and accompanying dance floor. In Happy Birthday, this stage is occupied by the Bandits of Rhythm.