Fatigue lifetime prediction methodology of the vulcanized natural rubber was proposed by incorporating the finite element analysis and fatigue damage parameter determined from fatigue test. Finite element analysis of 3D dumbbell specimen of natural rubber was performed based on a hyper-elastic material model determined from the tension, compression and shear tests. Stroke controlled fatigue tests were conducted using fatigue specimens at different levels of mean strain. The Green-Lagrange strain at the critical location determined from the FEM was used for evaluating the fatigue damaged parameter of the natural rubber. It was shown that the maximum Green-Lagrange strain was proper damage parameter, taking the mean strain effects into account. Fatigue lives of the natural rubber are predicted by using the fatigue damage parameters at the critical location. Predicted fatigue lives of the natural rubber agreed fairly well the experimental fatigue lives a factor of two.