The purpose of Virtual Traffic Light (VTL) applications is to increase traffic efficiency without the use of conventional traffic light infrastructure. With VTL applications, vehicles self-organize for intersection crossing based on wireless communication. Although VTL applications must comply with high safety requirements, no verification of VTL’s safety has been provided so far. We present a VTL protocol that is verified to be fail-safe using model checking as a verification approach. Performance evaluation through simulation showed that the verified fail-safe VTL protocol delivers—although far from optimum—decent results with respect to such traffic efficiency metrics like throughput and travel time. The investigated efficiency optimization substantially improved efficiency, yet compromised the safety of VTL. We quantify the tradeoff between efficiency and safety and show that increasing the safety level deteriorates efficiency only marginally. In particular, a safety level increase by a factor of 1,000 increases travel time by approximately 2% in the studied scenario. Therefore, high safety requirements can be met while maintaining high efficiency gains.