Abstract Two key goals of call admission control in the next generation wireless networks are efficient use of scarce wireless resource and quality-of-service improvement. As is well known, blocking handoff calls is normally more annoying than blocking new calls, whereas blocking new calls inevitably reduces resource utilization. That is, blocking new calls impact resource efficiency resulting in trade-off with handoff priority. A novel Mobility-Dependent Call Admission Control (MDCAC) scheme is proposed to achieve the aforesaid goals in a hierarchical cellular network. With MDCAC, new calls are accepted according to some acceptance probability, taking account of mobility difference between slow and fast mobility calls and mobility change over time. An iterative algorithm is developed to calculate performance measures of interest, i.e. new call blocking probability and forced termination probability under stationary scenarios. First, simulation results are shown to verify analytical results. Then, numerical results are presented to show the robustness of MDCAC. Last but not least, different CAC schemes are compared under non-stationary scenarios via simulation, where each cell (both microcells and macrocells) alternates between busy and normal states independently of one another. It is also shown that MDCAC outperforms the other CAC schemes under study.