For the East Trailhead:
From the Phoenix area, take I-17 North to exit 298 to HWY 179 West into Sedona. Follow the signs to 89A East. In 0.3 miles, turn left on Jordan Road. Drive 0.8 miles to the signed intersection with Park Ridge Drive. Turn left onto Park Ridge drive (Look for the trailhead hiking signs to help navigation) and drive 0.1 miles where the road will turn to a well graded dirt road. Take this dirt road an additional 0.5 miles to the well signed trailhead and parking. There are restrooms here but no water.
For the West Trailhead:
From the Phoenix area, take I-17 North to exit 298 to HWY 179 West into Sedona. At the junction with HWY-89A, follow the signs to 89A West. About 3.2 miles from the junction of HWY-179 and HWY-89A, turn right onto signed Dry Creek Road. Follow this paved road for 2.0 miles. Turn right at the signed intersection with FR152. Drive 2.4 miles on this rough dirt road to the signed parking area on your right for the Brin's Mesa trail.
Sedona has recently instituted a "Red Rock Pass", which is a fancy way of saying you need to pay to play. As of May, 2002, the fee is $5 per day per vehicle. There are plenty of places in and around Sedona to pay this fee and get the receipt, which you need to put on your vehicle dash to keep from being towed.
Hike Brin's mesa near Sedona, Arizona
There are two directions you can take this hike. When we hiked this, we parked at the easily accessed East trailhead, so this write up will reflect this. From the well signed East trailhead, take the easy to follow trail to the West. Although you're hiking through a pine forest at this point, there isn't much shade to be had... yet. To your right, you'll enjoy impressive views of Wilson Mountain. The trail then climbs pretty steeply up some slickrock steps to Brin's Mesa. Be sure to turn around once in a while to enjoy the increasingly impressive views of the Sedona area.
Brin's Mesa is more flat, barren, and wide open with 360 views of the area. You'll soon pass the signed junction with the Soldier's Pass trail (stay right). The trail then gently descends all the way to the west trailhead at Dry Creek road. After dropping off down the mesa, the pine trees are thicker here and provide some welcome shade. When you reach the West trailhead at Dry Creek Road, turn around and return the way you came...
You could detour back on the Soldier's Pass trail and take the Cibola trail back to the East Brin's Mesa trail. This way you get two hikes for the price of one. This makes for a total hiking distance of a bit over 8 miles. The trail junctions are all pretty well signed. Once you get on the Soldier's Pass trail you will get to enjoy the Arches, Seven Sacred Pools, and the sinkhole. Just after the sinkhole, look for a signed trail marking the Jordan trail on your left. Follow the Jordan trail about 0.3 miles to the signed junction with the Cibola trail (marked as Jct 2 on the map). Stay left to get on the Cibola trail and walk the final 0.6 miles to the East Brin's Mesa trailhead and your car. If you decide on this option, plan for about a 4.5 hour total hike.