To estimate an accurate travel direction of a user based on sensor signals from a mobile device being held by the user even if the user moves ahead while moving the mobile device right and left, a travel direction information output apparatus, a travel direction information output method, and a computer readable medium are provided, the travel direction information output apparatus including a travel direction estimation unit that calculates a travel direction of the user, a rotation amount calculation unit that calculates rotation amounts about a gravity axis of the mobile device being held by the user, and a selection unit that selects, based on an integrated value of the rotation amounts, from either to output travel direction information according to the travel direction calculated by the travel direction estimation unit or to output travel direction information that keeps previous travel direction information output.