Fatigue monitoring of the truss structure has been limited by the lack of amount of long-service sensors. This paper presents a more reflective strain-time histories estimation methodology based on Kalman filtering, which can be applied on the fatigue damage assessment of the unmeasured elements of the truss structure. Long-term fatigue information can be captured in real time through a digital wireless fatigue strain sensor. Non-white process noise is proccessed according to the virtual noise. The algorithm of the strain-time histories estimation has been verified by a numerical two-dimensional truss model. On this basis, the same experimental truss structure has been designed to demonstrate the methodology under a high-cycle fatigue testing. The results show a great deal of consistency between the estimated and measured strain values. Both the estimated and measured strain time histories are used for the fatigue damage assessment at the last section.