Methods and apparatus for improving the reporting of mobility information are disclosed. An example method, suitable for implementation in a mobile terminal such as an LTE UE, begins with the detecting (410) of a transition from idle state to connected state. The mobile terminal subsequently transmits (420) mobility information to the network in response to or in connection with the transition. The mobility information sent to the network includes one or more of several information elements or information types, including a list of recently visited cells, including information specifying a time-of-stay in each cell, or timestamp information that can be used to derive the UE's time in each cell. GPS-based speed information or other generic speed information may be included. Complementary methods for implementation in a base station and corresponding apparatus are also disclosed.