Andre Iguodala added a pair of late free throws and the Nuggets, who didn't arrive in the Bay Area until 3:30 a.m. following a late flight from Utah, held on for their fourth consecutive victory after opening the season 0-3.
Kenneth Faried added 18 points and 17 rebounds, while Iguodala had 19 points for Denver.
Klay Thompson led Golden State with 23 points, but the second-year guard missed a 3-pointer with 25 seconds left. Carl Landry added 22 points and nine rebounds off the bench, but the Warriors went scoreless over the final 2:47.
Denver shot just 38 percent from the floor and had trouble hanging onto the ball in the second half but put it together late to pull out the win.
Gallinari, who struggled with his shot most of the night, made the biggest shot with his tying slam dunk with 2.1 seconds left in the first overtime. Then he came up big in the second extra period after the Warriors built a 101-96 lead.
Gallinari made a 3-pointer to give Denver a 103-101 lead, and after Thompson missed 3, Iguodala sank two free throws and Gallinari added two of his own.
The Warriors, who trailed by 11 after the first quarter, couldn't muster another rally and lost for the third time in four games.
Golden State had a chance to win in the first overtime leading 94-92, but Thompson missed a pair of free throws with 13 seconds left.
Both teams also missed several chances to win in regulation.
The Nuggets led 86-82 late in the fourth quarter, then went scoreless over the final two minutes, while the Warriors missed three shots in the final minute, including a long jumper by Stephen Curry as the buzzer sounded.
The wild finish was in stark contrast to the first half, when Denver appeared on the verge of a blowout.
The Warriors, already without 7-foot center Andrew Bogut, were even more limited in their front court after sending Jeremy Tyler home because of an illness. That left only rookie Festus Ezeli and Andris Biedrins to handle the middle against a Nuggets team that went into the night leading the NBA in rebounding, points in the paint and second-chance points.
The results were predictable - at least early.
Denver dominated inside early, outscoring the Warriors 16-0 in the paint in the first quarter to go along with five blocked shots. Iguodala had 11 points in the period, including an emphatic dunk with 26 seconds left to cap a 10-0 run and give the Nuggets a seemingly comfortable 24-13 lead.
Golden State, coming off a 24-point loss to the Los Angeles Lakers on Friday, chipped away in the second quarter behind Lee and Thompson, then pulled within 40-39 at the half after Richard Jefferson scored on an alley-oop dunk.
The Nuggets maintained their slim lead going into the fourth but couldn't put the Warriors away in regulation.
Andre Miller added 15 points and eight assists for Denver, while Corey Brewer had 11 points.
(Copyright 2012 The Associated Press. All Rights Reserved)