The handoff failure probability has to be enhanced efficiently to enhance the performance of PCS system. In this paper a new scheme called velocity adaptive handoff algorithm for reducing handoff failure probability and maintaining the carried traffic constantly in PCS systems, by assigning low handoff threshold value for high mobility calls, and assigning high handoff threshold value for low mobility calls, is presented. The performance of evaluation of this new scheme is carried out in terms of tranffic characteristics. Also velocity estimation algorithm for this new scheme is presented. According to the result, the handoff failure probability of velocity adaptive handoff algorithm is enhanced about 60%.