Roman Martinez had 12 points and reserve Curtis Dennis added 11 as the Lobos (19-3, 5-2 Mountain West) won their fifth straight and beat a ranked opponent for the fourth time this season.
It was only the second time the Lobos and Cougars had both been ranked when facing each other. On Feb. 17, 1973, No. 18 New Mexico beat No. 20 BYU 76-66 in Provo, Utah.
The Lobos have defeated every Top 25 team they've faced this season, adding BYU (20-2, 5-1) to a list that includes California, Texas A&M and Texas Tech.
Gary finished 6 of 10 from the field and made 12 of 17 free throws in an entertaining matchup against BYU's Jimmer Fredette, who had 27 points. Jonathan Tavernari scored 10 of his 17 points in the second half, but it wasn't enough for the Cougars, the first team in the nation to reach 20 wins.
The matchup between Fredette and Gary was billed as a contest between two of the Mountain West's top point guards, and they delivered a great show.
Fredette, the league's leading scorer with an average of 20.2 points per game, has battled mononucleosis over the past several weeks, but New Mexico's defense did more to slow him down than his illness. He shot 8 of 21 from the field but made all seven of his free throws with seven assists.
Gary did his most important work down the stretch. He scored New Mexico's final seven points, and his two free throws with 35.2 seconds remaining put the Lobos ahead 73-67.
Fredette answered for BYU at the other end when he came off a screen and coolly hit a 3-pointer with 26.2 seconds to go, but Gary went 1 of 2 at the foul line with 25.8 seconds on the clock and then swished a pair of free throws with 12.5 seconds left.