When a user enters, initializes, or otherwise starts using a navigation function, such as a navigation function on a mobile phone or a stand-alone device, a current location is automatically estimated, prior to or in the absence of a GPS fix, for use as an origin in route determination. The estimation of current location is performed using a database of GPS fixes that are mapped to cell tower identifiers. For example, the database can include one or more fixes associated with each cell tower that the mobile device has used. Thus, when navigation on the device is begun, one or more cell towers to which the device can communicate are identified. If any has a GPS fix in the database, then a location derived from such GPS fix(es) can be used as an origin for navigation functions. Such navigation functions can include estimating a time of arrival at a destination, producing a route to the destination, and checking for traffic updates.