Provided are a method, system, and article of manufacture for maintaining message versions at nodes in a network. The nodes in the network maintain version information of nodes in the network. The version information for the nodes indicates a message version number of messages supported at the node. The nodes supporting one message version number can receive messages having that message version number. The nodes use the version information to determine whether there is at least one common message version number among the nodes The nodes supporting the at least one common message version number negotiate to join a quorum of the nodes having the at least one common message version number.