Coded cooperation that integrates channel coding in cooperative transmission has gained a great deal of interest in wireless relay networks. The performance analysis of coded cooperation protocol with multiple relays is investigated in this paper. We show that the diversity order achieved by the coded cooperation in a multi-relay wireless network is not only dependent on the number of cooperating relays but is also dependent on the code-rate of the system. We derive the code-rate bound, which is required to achieve the full diversity gain of the order of cooperating nodes. The code-rate required to achieve full diversity is a linearly decreasing function of the number of available relays in the network. We show that the instantaneous channel state information (CSI)-based relay selection can effectively alleviate this code-rate bound. Analysis shows that the coded cooperation with instantaneous CSI-based relay selection can achieve the full diversity, for an arbitrary number of relays, with a fixed code-rate. Finally, we develop tight upper bounds for the bit error rate (BER) and frame error rate (FER) of the relay selection based on coded cooperation under a Rayleigh fading environment. The analytical upper bounds are verified with simulation results.