Montoya was born in Peña Blanca, New Mexico. His parents, Thomas and Frances Montoya, were descendants of eighteenth-century Spanish immigrants to New Mexico. He received his early education in public schools in Sandoval County and graduated from Bernalillo High School in 1933. He continued his education at Regis College in Denver, Colorado. In 1935 he began law school at Georgetown University in Washington, D.C..

In 1937 at age twenty-two, while Montoya was still at Georgetown, he became the youngest representative in the history of the state to be elected to the New Mexico State House of Representatives. In 1938 Montoya graduated from law school and was reelected. The following year he was elected the Democratic majority floor leader.

Montoya continued his political ascent with his election to the New Mexico State Senate in 1940, once again becoming the youngest member of that body ever elected. By the time he left the Senate in 1946, Montoya had been twice reelected to the State Senate and held the positions of majority whip and Chairman of the Judiciary Committee. From 1947 to 1957 he was elected Lieutenant Governor of New Mexico three times and also served two additional terms in the State Senate.

In 1957 Montoya was elected to the U.S. House of Representatives in a special election after the sudden death of the recently reelected New Mexican Congressman Antonio M. Fernández. In Congress Montoya gained a recognition as a political moderate, a dedicated Democrat, and a diligent legislator -- qualities that earned him the esteem of his fellow legislators and made him an effective congressman. In 1963 he became a member of the House Appropriations Committee. He was a strong advocate of education measures and soon authored the Vocational Education Act. In 1964 he sponsored the Wilderness Act, which protected wilderness areas.

Montoya won the 1965 Senate election to complete the term of Dennis Chavez, who died in office, despite the fact the Governor of New Mexico, Edwin L. Mechem, had resigned the governorship in order fill the seat temporarily. Thus began an eleven year career in the Senate, where he served on the Appropriations Committee; the Public Works Committee; the Joint Committee on Atomic Energy; and most memorably, the Senate Select Committee on Presidential Campaign Activities, popularly known as the Senate Watergate Committee.

Montoya's most important accomplishment was his work on the Senate Agriculture Committee, where he gained expertise concerning the inspection and regulation of the meat packing industry. This led to an interest in consumer safety and health. He authored numerous pieces of legislation aimed at eliminating unsanitary conditions in the meat packing industry, including the Wholesome Meat Act of 1967, the Wholesome Poultry Act of 1968 and the Clean Hot Dog Act of 1974.

Montoya also worked on behalf of civil rights, education, health care, alien workers, and maintained a strong interest in the economic well-being of his constituents. In the health-care area he supported medicare, medicaid, and introduced a bill to provide bilingual training for those in the health care professions. Montoya also supported environmental protection, and programs to assist the elderly. His positions on the Joint Committee on Atomic Energy and the Senate Appropriations Committee allowed him to have a strong influence on maintenance of the federal installations in New Mexico.

In 1976 Montoya was defeated by Harrison Schmitt by over 16 points, the defeat is mostly contributed to the fact that Schmitt was a former astronaut and was a charismatic orator, something Montoya was not.