Foresighted, human-aware navigation is a prerequisite for service robots acting in indoor environments. In this paper, we present a novel human-aware navigation approach that relies on long-term prediction of human movements. In particular, we consider the problem of finding a path from the robot’s current position to the initially unknown navigation goal of a moving user to provide timely assistance there. The navigation strategy has to minimize the robot’s arrival time and at the same time comply with the user’s comfort during the movement. Our solution predicts the user’s navigation goal based on the robot’s observations and prior knowledge about typical human transitions between objects. Based on the motion prediction, we then compute a time-dependent cost map that encodes the belief about the user’s positions at future time steps. Using this map, we solve the time-dependent shortest path problem to find an efficient path for the robot, which still abides by the rules of human comfort. To identify robot navigation actions that are perceived as uncomfortable by humans, we performed user surveys and defined the corresponding constraints. We thoroughly evaluated our navigation system in simulation as well as in real-world experiments. As the results show, our system outperforms existing approaches in terms of human comfort, while still minimizing arrival times of the robot.