Energy harvesting (EH) cognitive relays are an exciting solution to the problem of inefficient use of spectrum while achieving green communications and spatial diversity. In a spectrum sharing scenario, we investigate the performance of a cognitive relay network, where a secondary source communicates with its destination over Nakagami-$m$ channels via decode-and-forward EH relays while maintaining the outage probability of the primary user below a predefined threshold. Specifically, we derive a closed-form expression for the secondary outage probability and show that it is a function of the probability of an EH relay having sufficient energy for relaying, which in turn, depends on the energy harvesting and consumption rates of the EH relay and the primary outage probability threshold. We also show that relaxing the primary outage constraint may not always benefit the cognitive EH relay network due to the limitations imposed on the relay's transmit power by the energy constraint.