Fatigue is one of the most widespread damage mechanisms found in metallic structures. Fatigue is an accumulated degradation process that occurs under cyclic loading, eventually inducing cracking at stress concentration points. Fatigue-related cracking in operating structures is closely related with statistical loading characteristics, such as the number of load cycles, cycle amplitudes and means. With fatigue cracking a prevalent failure mechanism of many engineered structures including ships, bridges and machines, among others, a reliable method of fatigue life estimation is direly needed for future structural health monitoring systems. In this study, a strategy for fatigue life estimation by a wireless sensor network installed in a structure for autonomous health monitoring is proposed. Specifically, the computational resources available at the sensor node are leveraged to compress raw strain time histories of a structure into a more meaningful and compressed form. Simultaneous strain sensing and on-board rainflow counting are conducted at individual wireless sensors with fatigue life prediction made using extracted amplitudes and means. These parameters are continuously updated during long-term monitoring of the structure. Histograms of strain amplitudes and means stored in the wireless sensor represent a highly compressed form of the original raw data. Communication of the histogram only needs to be done by request, dramatically reducing power consumption in the wireless sensing network. Experimental tests with aluminum specimens in the laboratory are executed for verification of the proposed damage detection strategy.