Estimating initial heading at start-up of navigation. At least some of the example embodiments are computer-implemented methods including: spawning a plurality of clone processes, each clone process given an identical location and speed, and each clone process given a unique direction; calculating, by each clone process, a respective position at the end of a frame period; terminating clone processes whose position at the end of the frame period is outside a predetermined threshold, the terminating results in remaining clone processes; and determining the heading of the mobile device from the remaining clone processes.