The idea of using knowledge of the current channel fading values to optimize the transmitted signal in wireless communication systems has attracted substantial research attention. However, the practicality of this adaptive signaling has been questioned due to the variation of the wireless channel over time, which results in a different channel at the time of data transmission than at the time of channel estimation. By characterizing the effects of fading channel variation on the adaptive signaling paradigm, it is demonstrated here that these misgivings are well founded, as the channel variation greatly alters the nature of the problem. The main goal of this paper is to employ this characterization of the effects of the channel variation to design adaptive signaling schemes that are effective for the time-varying channel. The design of uncoded adaptive quadrature amplitude modulation (QAM) systems is considered first, and it demonstrates the need to consider the channel variation in system design. This is followed by the main contribution of this paper; using only a single outdated fading estimate when neither the Doppler frequency nor the exact shape of the autocorrelation function of the channel fading process is known, adaptive trellis-coded modulation schemes are designed that can provide a significant increase in bandwidth efficiency over their nonadaptive counterparts on time-varying channels