Compressed natural gas (CNG) composite vessels for vehicles have been generally made of 34CrMo4 for a inner liner part and E-glass/epoxy for a composite layer part. But, there is a problem of material loss of CNG composite vessels used in vehicles due to the design of excessive thickness of the liner. And, light weight of the CNG composite vessel is required for improving fuel efficiency. In this study, optimal design for CNG composite pressure vessel was performed by using basalt fiber, which is the environment-friendly material having a good mechanical strength. The optimal thickness of each part (inner liner and composite layer) was determined by theoretical analysis and FEA for satisfying structural safety and lightweight of the vessel. Also, for improving fatigue life, optimal autofrettage pressure was derived from FEA results.