Video streaming is anticipated to dominate wireless traffic in the near future. We study wireless systems where an access point delivers video streams to multiple clients over unreliable wireless channels. The performance of each client is measured by the amount of time that its video playback halts due to buffer underflow, which has been shown to have the most impact on clients’ perceived quality of experience (QoE). This performance measure is significantly different from traditional quality of service metrics. We develop an analytic framework that jointly captures the video playback process and the unreliable and heterogeneous wireless channels. We use a diffusion limit to approximate the short-term QoE performance. We derive the capacity region for QoE by establishing a lower bound of a weighted sum of video halt durations over all clients. We then propose a QoE-optimal policy that can achieve every point within the capacity region. Finally, we compare our policy against two commonly used policies. Both theoretical analysis and simulation results show that our policy greatly outperforms other policies.