Procedural content generation is becoming an increasingly popular research area as a means of algorithmically generating scene content for virtual environments. The automated generation of such content avoids the manual labour typically associated with creating scene content, and is extremely useful in application areas such as computer graphics, movie production and video games. While virtual 3D caves are commonly featured in these virtual environment applications, procedural cave generation is not an area that has received much attention among researchers to date. This paper presents a procedural approach to generating 3D cave structures. Other than the development of a method to effectively automate the generation of visually believable 3D cave models, this paper also investigates how to efficiently construct and store this spatial information using a voxel-based octree data structure. In addition, the proposed approach demonstrates that caves with different characteristics can be generated by adjusting certain parameters in order to facilitate the creation of diverse cave structures.