Vermilion Cliffs Wilderness, Utah/Arizona. Straddling the border of Utah and Arizona, the Vermilion Cliffs Wilderness of Arizona combines with the Paria Canyons Wilderness of Utah to form one of the most wild and rugged landscapes on the Colorado Plateau. Deep, narrow canyons and high windswept mesas covered with swirling sandstone formations have made this area a must-see for travels from around the world. Vast fields of sand dunes covered this region 190 million years ago and have since consolidated into sandstone and uplifted as the entire region was subjected to colossal geologic forces beginning about 10 million years ago.