Dynamic selection of a protocol for communication between devices is disclosed. A first device may be connected to a second device by one or more communication links, such as a first communication link and a second communication link. Because the first device and the second device may not have pre-existing knowledge of what protocols are supported by the other device, the first device and the second device may perform protocol discovery by attempting protocols on the communication links in a coordinated manner. In this way, if a communication link becomes active between the first device and the second device, then a protocol attempted on the communication link may be supported by the first device and the second device, and thus may be used across the communication links. If multiple protocols are supported, then a preferred protocol is used across the communication links.