Multifractional Brownian motion (mBm) was introduced to overcome certain limitations of the classical fractional Brownian motion (fBm). The major difference between the two processes is that, contrarily to fBm, the almost sure \ho exponent of mBm is allowed to vary along the trajectory, a useful feature when one needs to model processes whose regularity evolves in time, such as Internet traffic or images. Various properties of mBm have already been investigated in the literature, related for instance to its dimensions or the statistical estimation of its pointwise \ho regularity. However, the covariance structure of mBm has not been investigated so far. We present in this work an explicit formula for this covariance. Since mBm is a zero mean Gaussian process, such a formula provides a full characterization of its stochastic properties. We briefly report on some applications, including the synthesis problem and the long term structure~: in particular, we show that the increments of mBm exhibit long range dependence under general conditions.