Bus timetables play an important role in improving the level of service and reducing operations costs of a bus transit system. Without dedicated bus lanes, bus travel times, which are important input data for bus timetabling, are usually time-dependent due to recurrent traffic congestion. However, few studies on bus timetabling have explicitly considered such travel time time-dependency in creating timetables. This paper addresses the problem of how to optimally modify an existing single-line bus timetable by slightly shifting vehicle departure times at the departure terminal and holding vehicles at other stops taking into account time-dependent travel times. The problem is mathematically formulated as a nonlinear programming model. According to the special structure and properties of the model, a derivative-free constrained compass search algorithm with revised step-size updating rule is applied to solve it. A case study of a bus line in Beijing, China is conducted to demonstrate the effectiveness and efficiency of the proposed model and solution algorithm. The case study results show that by utilizing the proposed methodology the optimized bus timetable can significantly reduce the total passenger travel time and improve ridership comfort, while rarely increasing the average vehicle cycle time. This study offers a promising and practical methodology for optimizing single-line bus service taking into account time-dependent travel times.