A fast Monte Carlo simulation scheme is newly developed for reliability analyses based upon a probabilistic model describing random fatigue crack growth driven by a noise of Poisson type. The proposed simulation scheme is based upon a probability measure transformation available for Lévy processes, which realizes an importance sampling principle so that very small probability of failure can be accurately estimated with small size of generated samples. First, a random differential equation is formulated for describing random fatigue crack growth by introducing a temporally inhomogeneous compound Poisson process as a driving noise. Next, a probability measure transformation for temporally homogeneous compound Poisson processes is applied to the random fatigue crack growth model by the use of a transformation technique of a time variable, which leads to a Monte Carlo simulation scheme realizing the importance sampling principle. Finally, through some numerical examples, it is clarified that the proposed simulation scheme can give accurate estimations for probability of fatigue failure with quite small sample size.