Wales went on to retain the 2013 RBS 6 Nations Championship later that season, under the stewardship of interim head coach Rob Howley, to add to Grand Slams in 2008 and 2011 and ensure the Gatland era is recorded as one of the most successful in Welsh history.
But, after a close fought double Test defeat on tour to Australia earlier in the summer of 2012, it is the Wallabies who have proved the most consistent 'thorn in the side' for the latest golden generation in Welsh rugby.
And returning head coach Gatland, the 15 Welshmen on tour and further six members of the Wales backroom staff who are on a summer sabbatical with the Lions, face the mouth-watering prospect of a Millennium Stadium encore against the world No2 side back on home turf on 30th November.
The four match Series first pits Wales against the might of South Africa, in the opening fixture on Saturday 9th November (5.30pm), before Argentina come to town on Saturday 16th November (2.30pm) and then Tonga on Friday night, 22nd November (7.30pm).
Whether the Wallabies arrive in Cardiff as Lion-tamers or with a point to prove against the Lions' Welsh contingent remains to be seen and is a question which will keep rugby fans around the world on the edge of their seats this summer.
But there is guaranteed to be unfinished business in some quarters when Australia boss Robbie Deans and Gatland meet head to head in a fourth and final international of 2013 regardless of what happens down-under this summer.
WRU chief executive Roger Lewis said: "Wales once again have the chance to test themselves against a selection of the very best sides in the world this Autumn.
"Our international planning is now well in place until 2019 - Welsh rugby fans can be confident of seeing the best teams in the world regularly over the coming years."
The current, double, RBS 6 Nations Champions are no strangers to facing the Wallabies - having played them six times in the last two years - and have beaten their Southern Hemisphere opponents as recently as 2008.
Of the Southern Hemisphere superpower nations Wales' record is best against Australia, showing ten victories for the Principality in 36 meetings with 25 losses and one draw (in 2006) in the 100-plus-year-old fixture.
And the clash this November comes after visits to the Millennium Stadium from the Springboks, the Pumas and Tonga, guaranteeing Gatland the chance to try to build momentum against the very best opposition.
Wales themselves will be fresh from a summer tour to Japan - led by caretaker coach Robin McBryde - and will meet up with their Lions counterparts looking for wins in November to further cement their status as champions of Europe after consecutive RBS 6 Nations titles in 2012 and 2013.
Australia captain James Horwill said: "Cardiff is one of the great destinations in world rugby. The population in Wales loves its rugby. They produce an enthusiasm and a fervor for the game, that rivals New Zealand, and South Africa in its intensity. But the Kiwis and the South Africans don't sing as well!"
Australia head coach Robbie Deans said: "You haven't experienced the passion and intensity of international rugby in totality until you have played Wales in Cardiff. Playing Wales there is one of the ultimate assignments in the game, especially in the recent era where they have been the dominant team in the Northern Hemisphere. I think our recent history shows that we have always lifted for those games as we've had to against a quality opponent. The numerous games against Wales in recent times have only enhanced the relationship and the rivalry between the two teams, not diminished it."
Autumn Series 2013 and 2014 RBS 6 Nations tickets will first be made available to WRU member clubs in 2013. For the best opportunity of securing a ticket the WRU urges members of the public to join their local rugby club where tickets will be available.
All home international tickets are initially distributed via the WRU member clubs or to debenture holders before any remaining seats are sold directly to the public. Pre-registration for the public is currently open and supporters can register via www.wru.co.uk/prereg, with any remaining tickets designated to be released for public sale on 22nd July, after clubs - and then WRU supporters clubs members - have received first refusal.
*The James Bevan Trophy has been contested when Wales have met Australia since 2008, named after Wales first captain of 1881 who went on to be an Australian national.
Wales International Fixtures Autumn Series 2013:
Wales v South Africa - Saturday, 9 November, Kick-Off 5.30pm - £70 / £60 / £40 / £25
Wales v Argentina - Saturday, 16 November, Kick-Off 2.30pm - £40 / £30 / £10 concession (U16) /£70 Family ticket 2 adults + 2 concession
Wales v Tonga - Friday, 22 November, Kick-Off 7.30pm - £25 / £10 concession/ £60 Family ticket 2 adult + 2 concession/ Minis/Juniors/Schools offer, with every 8 concessions purchased 2 adult tickets free
Wales v Australia - Saturday, 30 November, Kick-Off 5.00pm - £70 / £60 / £40 / £25