Clarke was drafted into the US Army and reported for induction in 1943. During his basic training in 1944, he married singer Carmen McRae. He went absent without leave for nearly four months, during which time he played with Cootie Williams and Dinah Washington, before being captured and sent to Europe. he eventually became part of the Special Services where he led and sang in chorales and performed on drums, trombone, and piano in various bands. While in Paris he met pianist and arranger John Lewis, with whom he began a long association.