We present the results of a multi-frequency study of the structural evolution of the VLBI jet in the BL Lac object 0716+714 over the last 10 years. We show VLBI images obtained at 5 GHz, 8.4 GHz, 15 GHz and 22 GHz. The milliarcsecond source structure is best described by a one-sided core-dominated jet of ~10 mas length. Embedded jet components move superluminally with speeds ranging from 5 c to 16 c (assuming z=0.3). Such fast superluminal motion is not typical for BL Lac objects, however it is still in the range of jet speeds typically observed in quasars (10 c to 20 c). In 0716+714, younger components, that were ejected more recently, seem to move systematically slower than the older components. This and a systematic position angle variation of the inner (1 mas) portion of the VLBI jet, suggests an at least partly geometric origin of the observed velocity variations. The observed rapid motion and the derived Lorentz factors are discussed with regard to the rapid Intra-Day Variability (IDV) and the gamma-ray observations, from which very high Doppler factors are inferred.