A large-scale multimedia server, in practice, has to service a large number of clients simultaneously. Given the real-time requirements of each client and the fixed data transfer bandwidth of disks, a multimedia server must employ admission control algorithms to decide whether a new client can be admitted for service without violating the requirements of the clients already being serviced. In this paper, we present an admission control algorithm for multimedia servers which: (1) exploits the variation in access times of media blocks from disk as well as the variation in client load induced by variable rate compression schemes, and (2) provides statistical service guarantees to each client. The effectiveness of the algorithm is demonstrated through trace-driven simulations.