In this paper we propose a new algorithm for selective relay strategies with Amplify-and-Forward (AF) relays which improves the relay network lifetime. The lifetime of the relay network is defined as the maximum number of messages which can be received with the desired SNR at the destination while the system Probability of Outage (P-outage) requirement is satisfied. The improvement in lifetime increases with the number of relays. When the number of relays is small, the method improves the lifetime under the condition of high initial relay energy levels. The proposed algorithm can be implemented in conjunction with previously proposed energy greedy relay selection strategies such as Minimum Power Transmission (MPT), Maximum Residual Energy (MRE), Minimum Energy Index (MEI), and Maximum Outage Probability (MOP).