The three-story red brick Lincoln Building opened in 1921. Located on the southeast corner of 18th and Vine, the Lincoln Building formed the cornerstone of the 18th and Vine District. The first floor featured Matlaw’s (a popular men’s clothing store) and other retail shops. Offices for dentists, doctors, and attorneys populated the second floor. Lincoln Hall occupied the third floor of the Lincoln Building.
On Friday and Saturday nights, Lincoln High School students flocked to Lincoln Hall to socialize and dance to bands. In July 1935, 14-year-old Charlie launched his career at Lincoln Hall with the Twelve Chords of Rhythm. The Chords were non-union, but made good money playing for the door. During the early 1940s, Charlie regularly played Lincoln Hall as a member of the Jay McShann and Harlan Leonard bands.