The use of High-pressure Vessel in eco-friendly Natural Gas Vehicles (NGV) is technologically feasible nowadays. Common applications of High-pressure Vessel are to carry Compressed Natural Gas (CNG), hydrogen for fuel-cell vehicle, and high-compression air in the new air-car technology. High-pressure Vessel is subjected to extreme compression-decompression cycles that could cause fatigue failure. Therefore, vessel shall be inspected regularly to detect if there is crack inside. The objective of this paper is to optimize the inspection interval of CNG Highpressure Vessel by means of Probabilistic Fracture Mechanics Analysis. Vessel is made of highalloy steel and assumed to have distributed elliptical cracks. Three length-to-depth crack ratios (a/c), i.e. 3, 8, and 15, are simulated. Crack is assumed to propagate in fixed ratio. Stress Intensity Factors at each crack tip are calculated by Finite Element Analysis and Crack Closure Technique. Fatigue crack growth is simulated by Cycle-by-Cycle Integration Technique. The Fracture Mechanics Analysis is then expanded to probabilistic analysis by considering stochastic nature of analysis parameters. Probability of failure is computed by Guided Direct Simulation Method using software which is specially written for this project . Based on simulation result, High-pressure Vessel is recommended to be inspected every 3 years.