Armstrong wurde 1901 in ärmlichen Familienverhältnissen in Storyville, dem Bordell-Viertel von New Orleans, geboren. Er wuchs bei seiner Mutter auf, die den Lebensunterhalt für die Familie als Hausangestellte und zeitweise auch als Prostituierte verdiente. 1913 kam er in ein Heim für farbige Waisen, wo er das Spiel auf dem Kornett