We consider a problem of asynchronous communication over a discrete memoryless channel (DMC). A transmitter seeks to communicate B bits of information to a receiver at a random time V. For a general distribution of V , we propose an asymptotically error-free variable length coding scheme that adapts the codeword length and distribution based on the arrival probabilities in a slot. For a simple class of L-step arrival distributions, we characterize the capacity of the DMC, and also show that the variable length coding scheme achieves higher rates and lower cost of communication in comparison with the fixed length coding scheme studied in prior works. Using numerical work, we illustrate our results for a binary symmetric channel in a number of interesting scenarios. © 1997-2012 IEEE.