Accies winger Dougie Imrie forced the only serious save of the 90 minutes with a brilliant 30-yard free-kick and the game looked destined to finish goalless.
But Vernon slotted home a dramatic late winner which could have a major say in the relegation battle and the nature of Aberdeen's season.
Aberdeen claimed their first win in eight games when Brown took charge for the first time at Hibernian on Boxing Day and this victory secured consecutive SPL successes for the club for the first time since August.
A crowd of 2,968 turned out for the afternoon kick-off as Accies played their first game of December and they looked short of sharpness, with the absence of injured pair Alex Neil and Nigel Hasselbaink proving a continued hindrance.
A tight contest was on the cards as soon as the team sheets came out with both Paixao twins dropped to the bench for Hamilton and Sone Aluko among the Aberdeen substitutes.
The pitch looked in good condition after passing an early-morning inspection after melting ice put the game under threat.
Hamilton had returned to the bottom of the SPL after Aberdeen's Easter Road triumph and they began brightly.
Jon Routledge sliced well wide after the Dons defence failed to clear Gavin Skelton's cross, and Derek Lyle saw his near-post effort saved by Jamie Langfield after Rory McArdle had misjudged a free-kick.
Aberdeen soon settled and Tomas Cerny made comfortable saves from Nikola Vujadinovic's header and a Josh Magennis strike, after centre-back Simon Mensing had missed a long ball.
The early half-chances quickly disappeared and neither side could gain the upper hand, although Hamilton were almost caught out by McArdle's long ball only for Chris Maguire to mis-control. Vujadinovic limped off in the 30th minute with Jerel Ifil coming on in his place in central defence.
Paul Hartley came close with a curling 30-yard free-kick before Imrie's effort from similar range surpassed the Aberdeen midfielder's strike. However, Langfield flew across to his left to touch the ball behind for a corner.
Damian Casalinuovo soon turned well after an Imrie cross but he could not keep his strike down.
Flavio Paixao replaced Casalinuovo in the 52nd minute and soon sent in a testing low cross following a sharp one-two with Grant Gillespie, but the Aberdeen defence eventually scrambled clear.
Aberdeen soon threatened when Maguire did well to get a cross in from the right but Vernon could not turn the ball on target.
Marco Paixao replaced Lyle in the 64th minute as Hamilton looked to inject some much-needed creativity into the game.
But the Dons looked the more likely team in the closing quarter and they shouted hopefully for a penalty as Mensing challenged Vernon from behind as the Dons briefly put their hosts under some aerial pressure.
Aluko replaced Magennis in the 78th minute and, despite some smart early touches from the winger, the match looked destined to head for a stalemate until he helped set up the winner 60 seconds into injury-time.
Vernon held the ball up and linked well with substitute Ryan Jack before slotting home from 12 yards to spark wild celebrations.
Hamilton 0-1 Aberdeen: Match Report - view commentary, squad, and statictics of the game as it happened.