A travel time information providing apparatus that provides a user with information regarding a travel time in a transportation network which is constituted by nodes and links and in which travel by train or bus is enabled, the travel time information providing apparatus comprising: a probability distribution storage unit configured to store first probability distribution data which expresses embarkation waiting times, each respective embarkation waiting time being a time from when the user arrives at any of the nodes constituting the transportation network until when the user embarks on a train or bus to depart from the node for each location where the waiting time occurs and second probability distribution data which expresses travel times, each respective travel time being a time necessary for the user to travel in any of the links constituting the transportation network for each location where the travel time occurs; a route acquiring unit configured to search a route connecting a point of origin and a destination and acquire a plurality of route candidates; a travel time calculating unit configured to calculate a probability distribution of a total travel time by acquiring all first probability distribution data corresponding to an embarkation waiting time which occurs on a respective candidate route and second probability distribution data corresponding to a travel time which occurs on the respective candidate route, and convoluting the acquired probability distribution data, for each of the route candidates; and an information providing unit configured to determine an estimated travel time and an evaluation value corresponding to each of the route candidates, both based on the calculated probability distribution of the total travel time, and output the estimated travel time and the evaluation value in a descending order of the evaluation values on the routes, wherein the evaluation value is higher when a median value or a mode value of the probability distribution of the total travel time is smaller, the evaluation value is higher when a variation of the probability distribution of the total travel time is smaller, the evaluation value is higher when a transportation fare is cheaper, and the evaluation value is higher when a number of transfers to another transportation means is smaller. a probability distribution storage unit configured to store first probability distribution data which expresses embarkation waiting times, each respective embarkation waiting time being a time from when the user arrives at any of the nodes constituting the transportation network until when the user embarks on a train or bus to depart from the node for each location where the waiting time occurs and second probability distribution data which expresses travel times, each respective travel time being a time necessary for the user to travel in any of the links constituting the transportation network for each location where the travel time occurs; a route acquiring unit configured to search a route connecting a point of origin and a destination and acquire a plurality of route candidates; a travel time calculating unit configured to calculate a probability distribution of a total travel time by acquiring all first probability distribution data corresponding to an embarkation waiting time which occurs on a respective candidate route and second probability distribution data corresponding to a travel time which occurs on the respective candidate route, and convoluting the acquired probability distribution data, for each of the route candidates; and an information providing unit configured to determine an estimated travel time and an evaluation value corresponding to each of the route candidates, both based on the calculated probability distribution of the total travel time, and output the estimated travel time and the evaluation value in a descending order of the evaluation values on the routes, wherein the evaluation value is higher when a median value or a mode value of the probability distribution of the total travel time is smaller, the evaluation value is higher when a variation of the probability distribution of the total travel time is smaller, the evaluation value is higher when a transportation fare is cheaper, and the evaluation value is higher when a number of transfers to another transportation means is smaller.