We present the long term evolution of the frequency-dependent X-ray time lags of the black hole candidate Cygnus X-1 as measured in 1996 and 1998 with the Rossi X-ray Timing Explorer (RXTE). Lag spectra measured during the 1996 June soft state are very similar to those seen during 1996 December and most of 1998 while Cyg~X-1 was in its hard state. During state transitions, however, the shape and magnitude of the X-ray lag is highly variable and tends to be much larger than outside of the state transitions. This behavior is most obvious in the 1--10 Hz band. The increase of the X-ray lag during the state transitions might be related to the formation and destruction of the synchrotron radiation emitting outflows present during the hard state.