Continuous-time random walks offer powerful coarse-grained descriptions of transport processes. We here microscopically derive such a model for a Brownian particle diffusing in a deep periodic potential. We determine both the waiting-time and the jump-length distributions in terms of the parameters of the system, from which we analytically deduce the non-Gaussian characteristic function. We apply this continuous-time random walk model to characterize the underdamped diffusion of single cesium atoms in a one-dimensional optical lattice. We observe excellent agreement between experimental and theoretical characteristic functions, without any free parameter.