Adaptive coded modulation is a powerful method for achieving a high spectral efficiency over fading channels. Recently proposed adaptive schemes have employed set-partitioned trelliscoded modulation (TCM) and have adapted the number of uncoded bits on a given symbol based on the corresponding channel estimate. However, these adaptive TCM schemes will not perform well in systems where channel estimates are unreliable, since uncoded bits are not protected from unexpected fading. In this paper, adaptive bit-interleaved coded modulation (BICM) is introduced. Adaptive BICM schemes remove the need for parallel branches in the trellis---even when adapting the constellation size, thus making these schemes robust to errors made in the estimation of the current channel fading value. This motivates the design of adaptive BICM schemes, which will lead to adaptive systems that can support users with higher mobility than those considered in previous work. In such systems, numerical results demonstrate that the proposed schemes achieve a moderate bandwidth efficiency gain over previously proposed adaptive schemes and conventional (nonadaptive) schemes of similar complexity.