The underlying structure of road networks (e.g., circuity, relative discontinuity) contributes to the travel time perception of travelers. This study considers additional factors (e.g., arrival flexibility, access to traffic information) and tests nonlinearities linking perception of travel time. These factors are linked to four categories according to time perception research in psychology: temporal relevance, temporal uncertainty, and temporal expectancies; task complexity, absorption, and attentional deployment; and affective elements. This study estimates the relationship on data collected from commuters recruited from a previous GPS-based study in the Minneapolis-St. Paul region consisting of trips from home to work and back. For these work trips, the subjects’ self-reported travel times and the subjects’ travel times measured by GPS devices were collected. The results indicate that nonlinearities are present for road network attributes. Furthermore, the additional factors (e.g., arrival flexibility, access to traffic information) influence the travel time perception of travelers.