A.H. Lawrence writes that the song originated from an off the cuff remark from Ellington. Nick Kenny had hailed a taxi, and offered to share it with Ellington. Kenny asked "Where to, Duke?", and Ellington replied "Drop me off at Harlem". Kenny then fashioned lyrics from Ellington's remark and presented him with them a few days later at the Cotton Club.