The first big hit version (#5 on the Billboard charts) was by Fats Waller recorded on May 8, 1935 (Victor 25044), reaching further heights in the charts (#3) for the Boswell Sisters in the following year (January 6, 1936—Decca 671 B (60302-A)).
The song had a major revival in 1957 in a recording (on April 3) by Billy Williams with orchestra directed by Jack Pleis. It reached #3 on the Billboard magazine charts. A reported million-seller, it was awarded a gold record.
Charlie Gracie (mostly known for his 1957 #1 hit "Butterfly" on Cameo Record label #105—45rpm) recorded "I'm Gonna Sit Right Down and Write Myself a Letter" (Cadillac Record label #141—45 rpm). The flip side of the record was a song written by Gracie, "Boogie Woogie Blues".