We consider a certain class of Riemannian submersions π : N → M and study lifted geodesic random walks from the base manifold M to the total manifold N. Under appropriate conditions on the distribution of the speed of the geodesic random walks, we prove an invariance principle, i.e., convergence to horizontal Brownian motion for the lifted walks. This gives us a natural probabilistic proof of the geometric identity relating the horizontal Laplacian Δ H on N and the Laplace-Beltrami operator Δ M on M. In the setting where N is the orthonormal frame bundle O(M), this identity is central in the Malliavin-Eells-Elworthy construction of Riemannian Brownian motion.