Popularity of Voice over IP (VoIP) applications such as Skype, Google Talk, and MSN Messenger along with emerging deployment of WiMAX networks is making VoIP over WiMAX an attractive market and a driving force for both carriers and equipment suppliers in capturing and spurring the next wave of telecommunications innovation, though challenges remain. Optimization of the VoIP call capacity over WiMAX networks is one such crucial challenge and remains an open research issue. While conventional scheduling methods have not considered the traffic characteristics of VoIP, in this paper, we propose a traffic aware scheduling algorithm for VoIP applications in WiMAX networks. We study the performance of our proposed method and compare it with that of some conventional methods. The tradeoff between delay and bandwidth efficiency is discussed, and it is shown that using our scheduling method enhances the efficiency of VoIP over WiMAX.