In this paper, we propose and analyse a new adaptive multilevel stochastic collocation method for randomized elliptic PDEs. A hierarchical sequence of adaptive mesh refinements for the spatial approximation is combined with adaptive anisotropic sparse Smolyak grids in the stochastic space in such a way as to minimize computational cost. We provide a rigorous analysis for the convergence and computational complexity of the adaptive multilevel algorithm. Two numerical examples demonstrate the reliability of an error control by adaptive methods and the significant decrease in complexity versus uniform spatial refinements and single-level stochastic sampling methods.