We consider a single source transmitting data to a single receiver/user over a wireless channel. The channel is time-varying, and the user has a buffer to store received packets before they are drained. At each time step, the source determines how much power to use for transmission. The sourceÕs objective is to allocate power in a manner that minimizes an expected cost measure, while satisfying strict buffer underflow constraints and a total power constraint in each slot. The expected cost measure is composed of costs associated with power consumption from transmission and packet holding costs. The primary application motivating this problem is wireless media streaming. For this application, the buffer underflow constraints prevent the user buffer from emptying, so as to maintain playout quality. We show that a modified base-stock policy is optimal under the finite and infinite horizon discounted expected cost criteria. For a special case, we present the sequences of critical numbers that complete the characterization of the optimal control laws in each of these two problems.