Valentine Stomp is another masterpiece in Fats Waller’s compositions. In 1925, after his divorce, Fats began frequenting many houses of prostitution in Harlem. He composed Valentine Stomp for Hazel Valentine who ran the "Daisy Chain", one of Fats' favourite establishment.

The introductory theme and the cascades full of energy quickly gives way to a theme full of fantasy in a minor key. This piece contains several Fats' recurrent themes and variations in the chorus.