For much of the past 600 million years the land that is now Red Rock Canyon National Conservation Area was the bottom of a deep ocean basin and the western coast of North America was in present day western Utah. A rich variety of marine life flourished in those waters and left behind deposits of shells and skeletons more than 9,000 feet thick which eventually compressed into limestone and similar carbonate rocks.

Beginning approximately 225 million years ago crustal movements caused the seabed to slowly rise. Streams entering the shallower waters deposited mud and sand which later consolidated into shales and marine sandstones. Changing land and sea level trapped large bodies of water which later evaporated leaving behind layers of salt and gypsum in some areas. Exposure of the sediments to the atmosphere allowed some of the minerals to oxidize, resulting in red and orange colored rocks. Streams meandering across the broad plain deposited sand, mud, gravel and other debris such as logs. In some cases, minerals in the groundwater replaced the organic materials in the buried logs forming petrified wood. Petrified wood is one of the few fossil remains found in the rocks at the foot of the cliffs.

About 180 million years ago the area was completely arid, much like the Sahara Desert is today. A giant dune field stretched from this area eastward into Colorado, and wind blown sand piled more than half-a-mile deep in some spots. As the wind shifted the sands back and forth, old dunes were leveled and new ones built up leaving a record of curving, angled lines in the sand known as "cross beds". These shifting sands were buried by other sediments, and eventually cemented into sandstone by iron oxide with some calcium carbonate. This formation, known locally as the Aztec Sandstone, is quite hard and forms the prominent cliffs of the Red Rock escarpment. In some areas the iron minerals in the rocks have been altered and concentrated giving the rock its red color.

The most significant geologic feature of Red Rock Canyon is the Keystone Thrust Fault. This fault is part of a large system of thrust faults that extend north into Canada and began to develop approximately 65 millions years ago. A thrust fault is a fracture in the earth's crust that is the result of compressional forces that drive one crustal plate over the top of another. This results in the oldest rocks on the bottom of the upper plate resting directly above the youngest rocks of the lower plate. At Red Rock Canyon, the gray carbonate rocks of the ancient ocean have been thrust over the tan and red sandstone in one of the most dramatic and easily identified thrust fault extends from the Cottonwood Fault along State Route 160 north for miles along the crest of the Red Rock escarpment. It then curves east along the base of La Madre Mountain before it is obscured by very complex faulting north of the Calico Hills.