One of the major challenges in transmitting real time video data in broadband wireless access (BWA) systems is that the bit rate of the video traffic varies from time to time, and hence the bandwidth utilization is low. To cope with the difficulties, we propose an enhanced uplink scheduling algorithm for variable bit rate video (VBR) traffic transmission in IEEE 802.16 BWA systems. In the proposed algorithm, the base station (BS) assigns uplink bandwidth to the video user by considering the traffic state transitions. The uplink bandwidth is divided into several intervals and each interval represents a traffic state. Only when the traffic state is changed, the bandwidth request process is incurred. Also, by using two reserved bits in the generic MAC header of IEEE 802.16 BWA systems as piggyback bits, the information of video traffic state transition can be sent to the BS without extra overhead. Simulations conducted with QualNet show that the proposed algorithm provides better performance in that the bandwidth waste ratio of our proposed algorithm is less than that of the conventional algorithms.