The design of various engineering structures, such as buildings, infrastructure, aircraft, ships, as well as microelectronic components and medical implants, must ensure an extremely low probability of failure (such as 10,-6) during their service lifetime. Such a low probability is beyond the means of histogram testing. Therefore, one must rely on some physically based probabilistic model for the statistics of structural lifetime. This study focuses on the structures consisting of quasibrittle materials, which are brittle materials with in homogeneities that are not negligible compared to structure size (exemplified by concrete, fiber composites, tough ceramics, rocks, sea ice, bone, wood, and many more at micro- or nano-scale). This paper presents a new theory of the lifetime distribution of quasibrittle structures failing at the initiation of a macro crack from one representative volume element of material under cyclic fatigue. The formulation of this theory begins with the derivation of the probability distribution of critical stress amplitude by assuming that the number of cycles and the stress ratio are prescribed. The Paris law is then used to relate the probability distribution of critical stress amplitude to the probability distribution of fatigue lifetime. The theory naturally yields a power-law relation for the stress-life curve (S-N curve), which agrees well with Basquin's law. The theory indicates that quasi-brittle structures must exhibit a marked size effect on the mean structural lifetime under cyclic fatigue and consequently a strong size effect on the S-N curve. It is shown that the theory matches the experimentally ob-served systematic deviations of lifetime histograms of various engineering and dental ceramics from the Weibull distribution.