Systems and methods for estimating time of arrival for vehicle navigation are described. One embodiment of a method includes determining a route for a vehicle to reach a destination from a current location determining, by the computing device, an estimated time for reaching the destination from the current location. Embodiments of the method additionally include determining, by the computing device, a current range of the vehicle, based on current fuel level and vehicle fuel efficiency and determining, by the computing device and based on the current range, whether the vehicle can reach the destination without refueling. Some embodiments include revising, by the computing device, the estimated time for reaching the destination to include a waypoint to refuel in response to determining that the vehicle cannot reach the destination without refueling and providing, by the computing device, the estimated time for reaching the destination for display to a user.