Communicating finite state machines (CFSM's) with FIFO (first in, first out) queues are used to model a protocol converter. A protocol conversion algorithm is developed and presented for the CSFM model of the protocols A and B. A converter H for protocols A=(A/sub 0/, A/sub 1/) and B=(B/sub 0/, B/sub 1/) is viewed as a black box such that H is between sender A/sub 0/ and receiver B/sub 1/. This gives a resulting protocol X=(A/sub 0/, H, B/sub 1/). The conversion algorithm requires a specification of the message relationships between the messages of protocols A and B. It is assumed that protocols A and B have the required progress properties. The algorithm includes a search for related messages from the two protocols in an FIFO from a composite space formed by a Cartesian cross-product of state spaces A/sub 1/ and B/sub 0/. The search produces finite-length traces which are combined to form a state machine H, which is examined for freedom from unspecified receptions, deadlocks, and livelocks. A protocol conversion example demonstrates the applicability of the algorithm.>