Since the early times caves were used as a place of worship. The oldest examples are known from the Stone Age, where caves were used for paintings, sketches and sculptures, many of them with a cultic background. Unfortunately we know very little about this, as we only have the artworks as remains of those people. But most prehistoric cave art is interpreted to have some kind of religious or shamanic background. Nevertheless, all attempts to explain the intentions are just fantasy. And there are other categories in the archaeology section.
The name cave church is not restricted to Christian churches, actually we include all underground spaces created for any kind of worship. There are caves of the Mithras cult, hellfire clubs of the 19th century and catacombs used by the Christians when they were persecuted in second and third century Rome. A better term is actually cave temple.
But temples or churches in caves are more than some paintings, some kind of altar, religious symbols, and enough room for the participants of services are signs of a church. The Mithras cult of ancient Rome was using solely caves for their divine service, due to the lack of enough caves they were mostly artificial. Buddhist temples are often installed in natural caves. Caves or temples were built inside natural caves and by excavating the temples from the massive rock.
The other cave churches we talk about on this page, are subterranea, which means artificial cavities, made by man. Often, when man had no natural caves for worship, he tried to build artificial caves replacing them. Sometimes it was an overhanging rock or a small cave which was widened until it fit the needs, sometimes it was a soft layer of rock which was used to dug out the cave for the church.