In this paper, we study Outage Probability (OP) and diversity order of a M-source and N-relay wireless network that combines Network Coding (NC) and Relay Selection (RS). More specifically, a Decode-and-Forward (DF) relaying protocol is considered and the network-encoding vectors at the relays are assumed to constitute a Maximum Distance Separable (MDS) code. Single Relay Selection (SRS) and Multiple Relay Selection (MRS) protocols are investigated, where the best relay and the L best relays forward the network-coded packets to the destination, respectively. An accurate mathematical framework for computing the OP is provided and from its direct inspection the following conclusions on the achievable diversity are drawn: i) the SRS protocol achieves diversity order equal to two regardless of M and N and ii) the MRS protocol achieves diversity order equal to L + 1 if L < M and equal to N + 1 if L >= M. These analytical findings are substantiated with the aid of Monte Carlo simulations, which also show that RS provides a better OP than NC based on repetition coding if L >= M.