Wedi methu sgorio cais yn erbyn Seland Newydd a De Affrica y mis hwn, pedwar munud yn unig gymerodd y tîm cartref i groesi yn erbyn y Wallabies wrth i Shane Williams orffen symudiad arbennig yn y gornel dde.
Tarodd yr ymwelwyr yn ôl yn syth wrth i'r clo Mark Chisholm redeg hanner hyd y cae ar ôl casglu pêl rydd, ond rhoddodd cais Lee Byrne wedi hanner awr fantais o 15-10 i Gymru wedi hanner o gyffro pur.
Roedd mantais Cymru yn wyth pwynt wedi 79 munud diolch i ddwy gic cosb a gôl adlam Stephen Jones.
Ymateb maswr Cymru Stephen Jones
Llwyddodd Digby Ioane i groesi yn yr eiliadau olaf a bu rhaid i Gymru amddiffyn am eu bywydau wedi hynny i sicrhau bod y fuddugoliaeth ddim yn llithro o'u dwylo.
Roedd y rhyddhad ar y chwiban olaf yn amlwg wrth i Gymru ennill am y tro cyntaf mewn 12 gêm yn erbyn un o fawrion hemisffer y de.
Cafwyd cychwyn llawn digwyddiad yn Stadiwm y Mileniwm wrth i gapten Awstralia Sterling Mortlock orfod gadael y cae yn sigledig ar ôl dau funud wedi gwrthdrawiad damweiniol gyda Jamie Roberts.
A dau funud yn ddiweddarach roedd Williams yn croesi yn y gornel i sgorio ei nawfed cais o'r flwyddyn.
Yr asgellwr bach eu hun sbardunodd y symudiad drwy hollti amddiffyn yr ymwelwyr ar y llinell hanner cyn i Roberts redeg yn glir.
Cafodd ei ganolwr ei ddal yn fyr o'r llinell, ond ailgylchwyd y bel yn sydyn ac roedd Williams yn y lle iawn i dderbyn pas Lee Byrne yn y gornel dde.
Parhau i edrych yn beryglus oedd tîm Warren Gatland wrth ennill tir yn gyson, ond yna sgoriodd Awstralia gais yn erbyn llif y chwarae.
Methodd Cymru a sicrhau'r bêl o linell yn hanner yr ymwelwyr, a chasglodd Chisholm y bêl rhydd a gwelodd bwlch enfawr o'i flaen ar ôl olwyr Cymru ymgynnull ochr arall i'r cae.
Ychwanegodd Giteau y trosiad, ac yna gôl adlam i roi ei dîm pum bwynt ar y blaen wedi 25 munud o chwarae cyffroes.
Caeodd Jones y blwch gyda chic cosb yn dilyn trosedd gan Stephen Moore a welodd bachwr Awstralia yn treulio 10 munud yn y gell cosb.
A gwnaeth Cymru yn fawr o'r dyn ychwanegol yn syth wrth i Williams dalu'r ffafr yn ôl i Byrne drwy roi cais ar blât i'r cefnwr gyda phas hyfryd. Rhoddodd trosiad Jones fantais o 15-10 i Gymru wedi hanner arbennig o rygbi.
Fe ddylai Martyn Williams fod wedi ymestyn y fantais eiliadau cyn y toriad, ond methodd a chasglu pas Gareth Cooper gyda'r ffordd yn glir i'r llinell gais.
Gwastraffodd Jones dau gyfle cymharol hawdd at y pyst yn 10 munud cyntaf yr ail hanner, ond roedd annel Giteau yn fwy cywir i gau'r bwlch i ddau bwynt.
Roedd dipyn llai o redeg cyffroes wrth i'r ddau dîm flino, ac roedd Jones yn ddigon bodlon i gicio gôl adlam mewn ymweliad prin yn hanner y Wallabies wedi goroesi 10 munud o amddiffyn.
Trodd Awstralia at nerth y blaenwyr yn y munudau olaf i geisio naddu ei ffordd drwy amddiffyn Cymru, ond safodd y tîm cartref yn gadarn yng nghysgod y pyst.
Roedd y fuddugoliaeth yn edrych yn saff pan giciodd Jones tri phwynt o gic cosb, ond roedd calonnau cefnogwyr yn eu gyddfau wrth i asgellwr Awstralia Ioane sgorio cais yn y funud olaf.
Methodd Giteau y trosiad a bu rhaid i Gymru amddiffyn am eu bywydau yn yr eiliadau oedd yn weddill a sicrhau bod cyfres yr hydref yn gorffen ar nodyn uchel.
Cymru: Byrne; M. Jones, Shanklin, J. Roberts, S. Williams; S. Jones, Cooper; Jenkins, Rees, A. Jones, Gough, A. Jones, R. Jones, M. Williams, Powell.
Eilyddion: Bishop am J. Roberts (18), D. Jones am Powell (62). Heb eu defnyddio: Hibbard, Yapp, Charteris, M. Roberts, Hook.
Ceisiau: S. Williams, Byrne. Tros: S. Jones. CC: S. Jones 2. Gôl adlam: S. Jones.
Awstralia: Mitchell; Hynes, Cross, Mortlock, Ioane; Giteau, Burgess, Robinson, Moore, Baxter, Chisholm, Sharpe, McMeniman, Waugh, Brown.
Eilyddion: Tuqiri am Hynes (34), Cooper am Mortlock (3), Freier am Moore (69), Mumm am McMeniman (69), Smith am Waugh (63). Heb eu defnyddio: Dunning, Cordingley.
Ceisiau: Chisholm, Ioane. Tros: Giteau. CC: Giteau. Gôl adlam: Giteau.
Cerdyn melyn: Moore (28).
Torf: 74,250
Dyfarnwr: Allan Lewis (Iwerddon).