The disclosure relates to estimating an initial position and navigation state associated with a vehicle using odometry and/or other data obtained from the vehicle to support dead reckoning at start-up. In particular, a last known position and last known heading at a first odometer value associated with the vehicle may be stored and compared to a current odometer value after linking a mobile device with the vehicle. The last known position and last known heading may be used to estimate the initial position and navigation state associated with the vehicle based on a difference between the compared odometer values. For example, the estimated initial position and/or navigation state may substantially correspond to the last known position and last known heading if the difference between the odometer values indicates no change, or a non-zero difference may define a radius to limit an estimated error associated with the initial position estimate.