Lost Heaven Queen es un barco de vapor de grandes dimensiones utilizado con propósitos de celebración y recreo y pertenece a la ciudad de Lost Heaven . Normalmente es anclado en el puerto de Lost Heaven en Central Island.
El barco de vapor por primera vez en ¡Feliz cumpleaños! , cuando Tommy Angelo asesinó al concejal durante su fiesta de cumpleaños celebrada a bordo del barco, a las órdenes de Don Salieri. Esta fué también la última aparición en el juego de la nave.
Lost Heaven Queen tiene tres cubiertas, la primera sobre todo es del personal del buque y área de trabajo, la segunda cubierta contiene un restaurante con un comedor al aire libre o terraza, así como un salón interior con un bar. La mayoría de los camarotes están ubicados en la segunda cubierta. La cubierta superior contiene los camarotes de primera clase, así como un escenario para músicos y bailarines y una pista de baile. En ¡Feliz cumpleaños! , el escenario está ocupado por Bandits of Rhythm.