Natural human locomotion contains variations, which are important for creating realistic animations. Most of all when simulating a group of avatars, the resulting motions will appear robotic and not natural anymore if all avatars are simulated with the same walk cycle. While there is a lot of research work focusing on high-quality, interactive motion synthesis the same work does not include rich variations in the generated motion. We propose a novel approach to high-quality, interactive and variational motion synthesis. We successfully integrated concepts of variational autoencoders in a fully-connected network. Our approach can learn the dataset intrinsic variation inside the hidden layers. Different hyperparameters are evaluated, including the number of variational layers and the frequency of random sampling during motion generation. We demonstrate that our approach can generate smooth and natural animations including highly visible temporal and spatial variations and can be utilized for reactive online locomotion synthesis.