The bridge is located within the Lake Mead National Recreation Area approximately 30 miles (48 km) southeast of Las Vegas, and carries Interstate 11 and U.S. Route 93 over the Colorado River.

It is jointly named for Mike O'Callaghan, Governor of Nevada from 1971 to 1979, and Pat Tillman, an American football player who left his career with the Arizona Cardinals to enlist in the United States Army and was killed in Afghanistan in 2004.

In March 2001, the Federal Highway Administration selected the route, which crosses the Colorado River approximately 1,500 feet (460 m) downstream of Hoover Dam.

In 1935, the American Association of State Highway Officials (AASHO, later AASHTO) authorized a southward extension of U.S. Route 93 from its previous southern terminus in Glendale, Nevada to Kingman, Arizona via Las Vegas, Boulder City, and a crossing of the Colorado River on the newly-constructed Hoover Dam (then known as Boulder Dam).

The approaches featured hairpin turns on both the Nevada and Arizona sides of the dam, and the terrain caused limited sight distances around curves.

[8] In March 2001, the Federal Highway Administration issued a Record of Decision indicating its selection of the "Sugarloaf Mountain Alternative" routing.

Security measures implemented following the September 11 attacks prohibited commercial truck traffic from driving across Hoover Dam.

[12] The composite design, using concrete for the arch and columns with steel construction for the roadway deck, was selected for schedule and cost control while being aesthetically compatible with the Hoover Dam.

[3] A permit problem between Clark County and the subcontractor Casino Ready Mix arose in May 2006 over the operation of a concrete-batch plant for the project, and this caused a four-month delay.

[17][18] Construction required hoisting workers and up to 50 short tons (45 t) of materials 890 feet (270 m) above the Colorado River using 2,300 ft (700 m)-long steel cables held aloft by a "high-line" crane system.

The bridge deck was fully paved in July, and the high-line cranes were removed from the site as the overall project neared completion.

[citation needed] O’Callaghan, a decorated Korean War veteran, was the Governor of Nevada from 1971 through 1979, and he was the executive editor at the Las Vegas Sun newspaper for many years until his death on March 5, 2004.

He gave up his multimillion-dollar career in the National Football League to enlist as an infantryman in the U.S. Army, and was killed by friendly fire in Afghanistan[27] on April 22, 2004.

Strong winds gusting across the Black Canyon on September 15, 2006, appear to have been the cause for the collapse of the "high-line" crane system that was used to carry workmen and materials at the bridge site.

[15][28] The reconstruction contract for the cranes was awarded to Cincinnati's F&M Mafco Inc. Work was halted when a Las Vegas construction worker, 48-year-old Sherman Jones, was killed.

Representatives of the Nevada Department of Transportation "are constantly monitoring the situation," and were "planning to discuss potential preventive measures on the bypass bridge" at their August or September 2012 meeting.