In recent years, a number of sophisticated architectures have been proposed to provide video-on-demand (VoD) service using multicast transmissions. Compared with their unicast counterparts, these multicast VoD systems are highly scalable and can potentially serve millions of concurrent users. Nevertheless, these systems are designed for streaming constant-bit-rate (CBR) encoded videos and thus cannot benefit from the improved visual quality obtainable from variable-bit-rate (VBR) encoding techniques. To tackle this problem, this paper presents a novel Slice-and-Patch (S&P) algorithm to support VBR video streaming in a multicast VoD system. Extensive trace-driven simulations were conducted to compare the performance of the S&P algorithm with two other algorithms based on priority scheduling. Results show that the S&P algorithm outperforms the other two priority scheduling algorithms for most videos. Compared with the CBR counterpart serving videos of the same average bitrate, the S&P algorithm is able to support VBR video streaming with an increase in latency of only 50%. Given that VBR-encoded video can achieve visual quality comparable to that of CBR-encoded video at half the bitrate, this S&P algorithm can potentially achieve performance comparable to that of CBR-based systems when combined with VBR encoding techniques.