Bristol skipper Iain Grieve went over for a last-minute try to secure only his side's second win of the season.
Trailing 22-8 at half-time, Nottingham turned it round with tries from Tim Streather, Tom Youngs and Alex Shaw to lead going into the final quarter.
But Bristol, whose first-half tries had come from Ross Johnson, Jack Adams and Mako Vunipola, fought back to win.
Nottingham's bonus-point defeat leaves them fifth in the Championship, 13 points behind leaders Worcester.
Bristol remain ninth, but have now moved nine points clear of bottom club Birmingham Solihull, ahead of next week's trip to second-placed London Welsh (23 October, 1500 BST).
Nottingham face another Sunday game next weekend at home to high-riding Bedford (24 October, 1500 BST).
Bristol coach Paul Hull told BBC Radio Bristol: "I am delighted. It was a tight game towards the end, but I thought we dominated in most parts. Hopefully that will turn a corner for us in our confidence as a team.
"We started the second-half very poorly and they scored 10 quick points which really put us on the back foot.
"When teams are in a losing streak, doubts start stepping in and that's what happened. But they powered through, stuck to their guns and scored an outstanding try.
"If we can keep performing with that intensity then we'll win more games than we lose."
"We also have an incredibly tough period towards the end of the first phase of the Championship, so there is no room for accepting that there will be times we cannot pick up points, because getting points all season long is what this league requires us to do.
Nottingham director of rugby Glenn Delaney said:
"We were obviously disappointed with the way the first half went and the way the game ended, but the fight back in the second half showed that we can perform on the road even when we know that things are going against us.
"There is no doubt that we are in a period of very tough games, but the key for us is to always go out to win, regardless of the team in front of us.
"There is no room for accepting that there will be times we cannot pick up points, because getting points all season long is what this league requires us to do."
Bookmark with:
What are these?