To meet the demands of green logistics while considering the time-dependent effects caused by traffic congestion, we establish a time-dependent green vehicle routing problem with time windows model for cold chain logistics. This model aims to minimize the total cost, including the transportation cost, refrigeration cost, carbon emission cost, and labor cost. Vehicles are allowed to wait to avoid a bad traffic environment after completing their services to customers. To solve the model, we develop a two-stage hybrid search algorithm. In the first stage of this algorithm, an adaptive large neighborhood search technique is used to determine the vehicle route, while in the second stage, a shortest-path algorithm is used to determine the departure time of the vehicles from customer’s node. Finally, numerical experiments are performed to verify the effectiveness and superiority of our model and the proposed hybrid search algorithm by comparing with the standard instances and large-scale instances.