The Traveling Salesman Problem (TSP) is an extensively studied NP-hard graph search problem. Many researchers pursued the most efficient and practical solutions, by applying various techniques to find the optimum or semi optimum solution (the one with least cost). There are numerous practical extensions and modifications of the original problem, such as The Time Dependent Traveling Salesman Problem (TD TSP). Indeed, the TD TSP was towards more realistic assessment of the traffic conditions of the original TSP. The edges between nodes are assigned different costs (weights), whether they are traveled during the rush hour periods or if they crossed the traffic jam regions (such as city centers). In the classic TD TSP, the edges are assigned higher costs using concrete numbers, which might be looked at as a limitation; because those jam factors are non-deterministic and better be represented by fuzzy numbers. In this paper we introduce a more realistic novel fuzzy-based extension, the IVFSSTD TSP (Interval-Valued Fuzzy Soft Set for the Time Dependent Traveling Salesman Problem). Our core concept employs interval-valued fuzzy soft sets on the costs between nodes to realistically quantify the traffic jam regions, and the rush hours periods effects on any tour, then we user the arithmetic mean operator to take in account all factors affecting an edge simultaneously, which lead to less information loss and more adequate representation for the jam factors. Since the interval-valued fuzzy soft sets are generalization of the original fuzzy sets, which has the ability to simulate uncertain road conditions more efficiently than concrete numbers, then our approach can be considered a useful extension and a practical alternative model of the original abstract problem.