MEMS-based storage is an emerging storage media that can be used in the wide areas of future applications. One of the killer applications for this storage is multimedia streaming service. With the recent proliferation of video-on-demand services, performance bottleneck of I/O subsystems in streaming media is becoming increasingly serious. MEMS storage can bridge the performance gap between DRAM and disk with low cost. This paper presents data allocation and caching algorithms for multimedia streaming service with MEMS storage. The algorithms incorporate prefix-aware caching into existing algorithms to improve the performance of streaming servers. Trace driven simulations with real world VOD traces show that the proposed algorithms improve the performance of multimedia streaming servers significantly in terms of the cache miss penalty and the startup latency.