The rolling element bearings are extensively applied in rotating machines, and they are the most susceptible components in rotating machines. Early fault detection of bearings is to prevent machines from such typical failures and subsequent consequences. In this paper a detector based on Ensemble Average of Autocorrelated Envelopes (EAAE) is proposed to identify the early occurrence faults in rolling element bearings, of which the fault induced vibration signals are inevitably contaminated or masked by both additive background noise and random phase noise (or slippage between bearing components). To enhance the cyclostationary characteristics for fault detection, it utilizes the phase synchronization property of autocorrelation signals for aligning the cyclostationary signals in the lag domain to achieve an effective ensemble average which allows both types of random influences to be suppressed significantly. As a result, this detector shows very high performance of robustness in extracting the local fault signatures, which is verified by simulation signals and experimental investigations and benchmarked by the recent milestone method of Spectral Correlation (SC).