We study optimal rate control for transmitting deadline-constrained data over a time-varying channel. Specifically, we consider a wireless transmitter where the channel gain varies stochastically over time and the packets in the queue have strict delay constraints. The transmitter can adapt the rate over time by varying the power and the goal is to obtain the rate-control policy that minimizes the expected energy expenditure while meeting the deadline constraints. We first consider the case of B bits of data that must be transmitted by a deadline T and using a novel continuous-time stochastic control formulation obtain the optimal policy. Based on a cumulative curves methodology and a decomposition approach, we then obtain the optimal policy when the queue has packets with variable deadline constraints. Finally, we present a heuristic policy for the case of arbitrary packet arrivals to the queue and compare its performance using simulation results with a non-adaptive scheme.