In this paper, we investigate call admission control (CAC) with opportunistic scheduling and propose a novel CAC algorithm for users with quality of service (QoS) requirements. Our main contribution is threefold. First, we verify that, compared with several other scheduling schemes, cumulative distributed function based scheduling (CS) makes the best tradeoff between efficiency and fairness in full-load scenario and exploits the best opportunism with absolutely fair resource allocation. Then we deduce and validate the multi-user diversity gain (MDG) of CS, which determines its long-term average performance and is used for estimation of resource occupation in CAC algorithm design. After that, we use opportunistic round robin (ORR) method to calculate the statistical low performance bound of CS, and propose CS/ORR based CAC (COCAC) algorithm, which guarantees the heterogeneous minimum rate requirement (MRRs) of both new access users and existing ones. Finally, we evaluate the performance of the proposed COCAC algorithm via simulation. Results show that COCAC can significantly reduce new call block probability, effectively make use of system resources, as well as strictly guarantee all users' MRRs.