For an engineering structure with an actual fatigue life over that corresponding to a so-called fatigue limit, appropriate reliability assessment and fatigue life prediction are essential for developing the structure and sustaining its high quality in service. Basic clues are explored. A competition fatigue initial mechanism is shown to provide a requirement of material primary quality management. Affordable deduced material and structural probabilistic S-N curves are presented by fitting into material mid-and-long life S-N data and fatigue limits and, then, comparing to structural fatigue limits. Random cyclic stress-strain relations are depicted for constructing random stressing history of structures. Reliability assessment and fatigue life prediction are established to synthetically consider the interference of applied stresses deduced from the random cyclic stress-strain relations and capacity strengths derived from the structural S-N relations with an expected life. Affordable and appropriate method has been then developed to realize the reliability assessment and fatigue life prediction including the super long life regime. Availability of the present method has been indicated through a reliability analysis to the velocity related reliabilities and fatigue lives of a railway axle.