Former Scotland boss Brown and his assistant Archie Knox quit Motherwell on Thursday, agreeing two-and-a-half-year deals at Pittodrie on Friday, but after nine minutes they may wish they had stayed at Fir Park after goals from David Templeton and Rudi Skacel.
Stephen Elliott, Skacel and substitute Arvydas Novikovas were on target in the second half to propel Hearts to a fifth straight win to consolidate their third-placed position behind Rangers and Celtic.
For Aberdeen it was a 12th loss of the season and a seventh in succession, leaving them level with Hamilton at the foot of the SPL, with Accies having a game in-hand and now a better goal difference.
Hearts were playing for the first time since November 20 having twice been thwarted by the arctic weather before a thaw allowed Saturday's game to go ahead.
A trip to Motherwell was rearranged for next Tuesday, where Hearts manager Jim Jefferies was expecting to see Brown, but the duo met a few days earlier.
Brown's first match in charge of Well was also at Tynecastle, losing 1-0 on December 30, 2009.
Almost a year on, 70-year-old Brown and Knox - assistant to Sir Alex Ferguson as Aberdeen enjoyed domestic and European success in the 1980s - were tasked with revitalising the Dons, who parted company with Mark McGhee earlier this month.
Brown and Knox watched from the stand as Neil Simpson and Neil Cooper took charge today, but the depth of the Dons' predicament was soon confirmed as Hearts went 2-0 up inside nine minutes.
After Zander Diamond flashed a header wide, Hearts took a fifth-minute lead through Templeton.
Skacel and Templeton combined on the left and Chris Maguire's clumsy challenge could have seen the hosts awarded a penalty.
Templeton, though, with Elliott nearby, hooked the ball in despite the presence of two defenders on the line.
Templeton was to the fore for the second, running down the left before playing a ball across the area for Skacel to side foot in.
Skacel and Ian Black were both booked after a free-kick taken too quickly for referee Mike Tumilty's liking, the latter for dissent having pointed out it was he not his team-mate who had taken the kick before the whistle.
Templeton then flashed a shot across goal narrowly wide as he continued to trouble Dons right back Jerel Ifil.
Hearts continued to dominate, with the Dons poor and Brown was seen at the touchline consulting with Cooper and Simpson even before the half-time whistle, working out how to overturn the deficit.
Two Hearts goals soon after the restart all but confirmed defeat for Brown and the Dons.
After 51 minutes, Marius Zaliukas won the ball at the halfway line under the challenge of Paul Hartley, the ball was worked wide to the left and Palazuelos' cross was perfectly weighted for Elliott to stoop low and head in.
Hearts cut through the desperate Dons defence once again seven minutes later to net a fourth.
Adrian Mrowiec's cross from the right found Templeton, who might have scored himself but he squared the ball for Skacel to tuck in unopposed from a yard out.
It was the Czech Republic midfielder's seventh of the season since beginning his second spell at Tynecastle in September.
Jamie Langfield denied Skacel a third, racing off his line to save at the Hearts midfielder's feet after Kyle's flick on before Hearts netted a fifth.
Novikovas scored seven minutes after coming on as a substitute for Templeton.
The Lithuanian netted a fine individual goal, cutting in off the wing and firing a right-foot shot into the top corner after 77 minutes.
Substitute Calum Elliot lofted the ball over as Hearts went close to a sixth but Jefferies' men had to settle for five.