Location management is one of the fundamental issues in cellular networks. It includes two operations: location update and paging. The goal of location management is to minimize the combined cost of these two operations. Recently a distance-based scheme using a pre-defined look-up table for location updates has been proposed. The table describes the relationship between the distance and the time: the distance decreases while the time increases. In this scheme, the paging area for a mobile station will be automatically reduced if the mobile station does not update its location over a certain time period. Therefore this scheme performs quite well when a mobile station travels at a low speed. However, it does not perform well when the speed of a mobile station is high or when the incoming call arrival rate is high. To overcome these drawbacks, a speed-adaptive location management scheme is proposed in this paper. The proposed scheme uses an enhanced look-up table. The table consists of two parts: the distance in the first part increases while the time increases; in the second part, the distance decreases with the increasing time. To reduce the paging cost of high-speed mobile stations further, the concepts of speed ranges and paging polar angles are introduced in the scheme. Numerical simulations using activity-based, random walk and fluid flow mobility models have shown that the proposed scheme performs well for mobile stations traveling at a high speed as well as for those traveling at a low speed.