Previous studies on video storage servers focused on improving the disk throughput and reducing the server buffer size. However, the initial delay of a new request, one of the most important quality of service (QoS) parameters from the users' point of view, is almost neglected while designing a storage subsystem or evaluating its performance. For different types of video-on-demand (VOD) services such as interactive video game, digital library, or movie-on-demand system, the initial delay can vary from 0.5 s to 5 min. This criterion brings some impacts on designing a storage server for a particular VOD application. In this paper, we investigate the storage server design and the performance evaluation of VOD systems with different initial delay guarantees. We propose a new performance model on evaluating the efficiency of a video storage server so that a cost-effective configuration can be easily obtained under a specified initial delay bound.