We consider a certain class of Riemannian submersions $π: N \to 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 particular, when $N$ is the orthonormal frame bundle $O(M)$, this identity is central in the Malliavin-Eells-Elworthy construction of Riemannian Brownian motion.