Summary: We analyze time-discrete and time-continuous ‘fractional’ random walks on undirected regular networks with special focus on cubic periodic lattices in \(n=1,2,3,\ldots\) dimensions. The fractional random walk dynamics is governed by a master equation involving fractional powers of Laplacian matrices \(L\frac\alpha2\) where \(\alpha=2\) recovers the normal walk. First we demonstrate that the interval \(0<\alpha\leqslant2\) is admissible for the fractional random walk. We derive analytical expressions for the transition matrix of the fractional random walk and closely related the average return probabilities. We further obtain the fundamental matrix \(Z^{(\alpha)}\), and the mean relaxation time (Kemeny constant) for the fractional random walk. The representation for the fundamental matrix \(Z^{(\alpha)}\) relates fractional random walks with normal random walks. We show that the matrix elements of the transition matrix of the fractional random walk exihibit for large cubic \(n\)-dimensional lattices a power law decay of an \(n\)-dimensional infinite space Riesz fractional derivative type indicating emergence of Lévy flights. As a further footprint of Lévy flights in the \(n\)-dimensional space, the transition matrix and return probabilities of the fractional random walk are dominated for large times \(t\) by slowly relaxing long-wave modes leading to a characteristic \(t^{-\frac{n}{\alpha}}\) -decay. It can be concluded that, due to long range moves of fractional random walk, a small world property is emerging increasing the efficiency to explore the lattice when instead of a normal random walk a fractional random walk is chosen.