In this work, we discuss how to support Video-on- Demand service in multi-hop WiMax mesh networks. We are interested in the scenario that end users connect to the video servers through the base station of the multi-hop WiMax networks. We propose a model that can jointly solve the admission control and channel scheduling problems. Our proposed approach guarantees the required data rate is achieved for video streams, which is crucial for multimedia streaming applications. An efficient multicast routing technique is also proposed to minimize the bandwidth cost of joining a multicast tree. Furthermore, we adopt the application layer Patching technique to accommodate end users that join a video multicast group at different times. Overall, our solution efficiently utilizes the bandwidth resource of the networks and provides data rate guarantee for video streams. Simulation study shows that with the proposed approach, true Video-on-Demand in WiMax mesh networks can be achieved under high video request arrival rate.