In this paper, a novel orthogonal frequency division multiplexing (OFDM) scheme, called OFDM with index modulation (OFDM-IM), is proposed for operation over frequency-selective and rapidly time-varying fading channels. In this scheme, the information is conveyed not only by M-ary signal constellations as in classical OFDM, but also by the indices of the subcarriers, which are activated according to the incoming bit stream. Different low complexity transceiver structures based on maximum likelihood detection or log-likelihood ratio calculation are proposed and a theoretical error performance analysis is provided for the new scheme operating under ideal channel conditions. Then, the proposed scheme is adapted to realistic channel conditions such as imperfect channel state information and very high mobility cases by modifying the receiver structure. The approximate pairwise error probability of OFDM-IM is derived under channel estimation errors. For the mobility case, several interference unaware/aware detection methods are proposed for the new scheme. It is shown via computer simulations that the proposed scheme achieves significantly better error performance than classical OFDM due to the information bits carried by the indices of OFDM subcarriers under both ideal and realistic channel conditions.