A travel direction determination apparatus is provided, including: a sensor signal acquisition unit that acquires sensor signals from sensors mounted in a mobile device; a first travel direction calculation unit that calculates a travel direction of the user without relying on a walking state of the user; a second travel direction calculation unit that calculates the travel direction of the user based on the sensor signals when the user who holds the mobile device is in a walking state; and a determination unit that determines the travel direction of the user first to the travel direction calculated by the first travel direction calculation unit, and then to the travel direction calculated by the second travel direction calculation unit, responding to changes in the state of the user from non-walking state to walking state.