The Paris-Erdogan law describes the rate of fatigue crack growth as a function of the amplitude of the applied stress intensity factor. This equation, however, does not include a dependence of the crack growth on the structure size, which has been observed experimentally for concrete. The size effect on the fatigue crack growth is derived based on two hypotheses: (1) the scaling of the critical energy dissipation for fatigue crack growth has the same form as that of fracture energy for monotonic loading; (2) the difference in transitional sizes between the fatigue and monotonic loading is purely due to the difference in the fracture process zone (FPZ) size. The size-dependent fatigue crack growth law is verified experimentally through size effect tests on Berea sandstone. Using digital image correlation, it is shown that the FPZ length is approximately 7 mm and 11 mm for monotonic and cyclic loading, respectively. Optimal fitting resulted in transitional sizes of 34 mm and 54 mm for monotonic loading and cyclic loading, respectively, which shows a proportional relationship between the FPZ length and the transitional size.