This paper presents an approach for verifying and validating time-dependent protocols, i.e. protocols for which the time spent for the functions is critical to a successful execution. The proposed approach is a novel modification of the traditional Unique Input/Output (UIO) method by explicitly taking into account the time specification of each edge in a protocol modeled as a finite state machine (FSM). A new FSM model which characterizes the timing properties of the protocol, is proposed. An algorithm which generates a test sequence with minimal traversal time for a time-dependent protocol in polynomial time complexity, is proposed.