The home side had new signings Bailley Collins and Chloe Fitzpatrick on the bench whilst the visitors handed debuts to Norwegian midfielder Stina Kleppe and recent signing from St Johstone, Rebecca Foote.
It was the away side that started the brighter of the two teams and they were reward with goal after just five minutes. Tammy HARKIN made her way forward from the centre of the park before firing a left shoot in off the post from 25 yards out.
The Dons looked to reply almost immediately as Eva Thomson played in Francesca Ogilvie who rounded the keeper before Jade McLaren got back to clear. The visitors were clearly buoyed by their early goal though as they took charge of early stages and doubled their lead after 16 minutes.
Goalscorer Harkin swung a cross in from the left which Gail Gilmour punched clear but the ball fell at the feet of Steffi SIMSON who knocked the ball in from close range to double United's lead.
The Dons started to work their way back into the match as they recovered from the set back of losing two early goals. Chloe Gover was unlucky not to pull one back in the 23rd minutes as she saw her curling 30 yard free-kick clatter the United crossbar.
Gover again had a chance when she robbed McLaren on the edge of the box but couldn't keep her shot down as it flew over the bar. The away team still looked dangerous as Danni McGinley saw her powerful shot deflected over the Aberdeen goal.
The hosts had fully found their feet after half an hour as they took back control from United. A good ball forward by Carrie Doig found Loren Campbell on the right and her cross was headed wide by Bayley Hutchison.
There were 39 minutes on the clock when Aberdeen gave themselves a lifeline back into the game. A driving run by Campbell down the right earned her side a corner which Gover went over to take. Gover's dangerous in-swinging corner was met by Eilidh SHORE who headed into the net from close range.
The goal clearly lifted the home side who went in search of an equaliser before half-time with both Hutchison and Ogilvie forcing saves out of United keeper Aaliyah-Jay Meach but the visitors went into the break in front.
Aberdeen looked like they meant business at the start of the second period as Thomson went close with a low shot before McLaren cleared a dangerous looking Ogilvie cross. Despite their bright start to the half, the Dons found themselves two behind again on 50 minutes.
Holly Napier's pass found Kleppe in space at the edge of the box and the Norwegian steadied herself before placing a side foot finish beyond Gilmour for 3-1.
The goal could well have taken the wind out of Aberdeen's sails but to their credit, they came firing back. Amy Strath and Bailley Collins replaced Carrie Doig and Kelly
Forrest on the hour as the hosts looked to change things up and they were almost instantly rewarded as Thomson set up Hutchison who couldn't direct her shot either side of Meach.
Aberdeen had a second on 63 minutes courtesy of a fine goal. OGILVIE ran onto a through ball and as she approached the right side of the eighteen-yard box, clipped a wonderful finish over Meach and into the United net.
The hosts were in the ascendancy now as they went in search of an equaliser in final twenty minutes and they made another change with Johan Fraser replacing Chloe Gover.
A good turn and cross from Thomson saw the ball flash across the United goal but nobody was there to turn it in.
It was nearly 3-3 in the 79th minute as a great ball forward by Collins found Ogilvie who cut in from the left. Ogilvie might have squared the ball across goal but instead fired a powerful shot towards the near post which Meach did really well to parry around the post.
The pressure was building on United as the game entered the final ten minutes and they themselves always appeared dangerous on the counter. All the play was in the visitors half though and the Dons finally got themselves level with five minutes remaining.
Thomson played a neat ball between two United defenders to find HUTCHISON running through on goal and she fired an unstoppable right foot finish into the top corner for a deserved equaliser.
A draw from 3-1 down seemed like a pretty good return but the Dons were having none of it and went in search of a late winner.
It seemed they had missed their last chance in the second minute of stoppage time as Thomson picked up an Ogilvie free-kick but fired her shot straight at Meach.
The hosts were rewarded for their efforts as they grabbed all three points with 94-minutes on the clock.
THOMSON gathered outside a crowded penalty area before sending a stunning strike into the top corner of Meach's net with virtually the last kick of the ball to make it 4-3 and complete a tremendous fightback.
Loren CAMPBELL:
"It was a very competitive game and to be honest we started really slowly.
"I think it was our own fault that we were down a couple of goals but to come back and have the determination to turn a three-one into a four-three is a really positive way to start the season.
"The third goal was a blow early in the second half but we had chances in the first half so we were confident that we had two or three goals in us.
"The girls had the determination and we always have the belief that we've got more goals in us than the opposition.
"We went for it at the end, changed our formation and went very attacking.
"Cormack park is big pitch and I felt that we were fitter today and I think the fact we play a lot of wide football, Dundee United struggled with that and we managed to tire them out.
"The style of football that we play, I think finishing teams off in the last five or ten minutes is something that we're going to do a lot of this season."
Eva THOMSON:
"The first twenty minutes we were quite shaky and we were two-nil down in that twenty minutes but in the second part of the first half we started to play our football more.
"We were getting the ball out wide and getting crosses in and started to create some chances then getting the goal to go in at two-one at half time we had the momentum going into the second half.
"When we went three-one down our heads didn't really drop and we picked ourselves up and went again and getting the goal for three-two really boosted the team.
"Getting the third goal and then the last minute one felt really good.
"I knew there wasn't that long left because I knew there was eleven minutes to go at three two so I knew my goal was late but I didn't realise it was that late until the final whistle blew thirty seconds later.
"It's a really good start getting three points from the first game."