Sgoriodd y capten wedi hanner awr o chwarae wrth fynd heibio James Collins llawer yn rhy hawdd ac yna churo Wayne Hennessey ar ei bostyn agosaf.
Daeth y gôl wedi cyfnod o bwyso gan y tîm cartref, wrth i Gymru fethu â chadw meddiant na chynnig unrhyw fygythiad wrth ymosod yn y gêm yng Nghrŵp G rowndiau rhagbrofol Ewro 2012.
Gorffennodd Cymru yn gryf a gwelodd Simon Church ei beniad yn adlamu'n ôl oddi ar y trawst pum munud o'r diwedd.
A thri munud yn ddiweddarach roedd yr eilydd yn meddwl ei fod wedi cipio gêm gyfartal ond cafodd ei ddathliadau eu difetha wrth i'r llumanwr weld camsefyll.
Cyn hynny, llwyddodd Gareth Bale i greu dau agoriad wrth groesi ar draws wyneb y gôl ond doedd neb yno i fanteisio.
Ond yn y cefn oedd Cymru yn edrych yn fwyaf bregus, wrth i Sam Ricketts gael ei guro nifer o weithiau, tra bod Ashley Williams a James Collins yn cael eu tynnu'n rhy bell o'i gilydd.
A seren y gêm Vucinic oedd yn bennaf gyfrifol am hynny wrth i bob ymosodiad y tîm cartref fynd drwy ymosodwr Roma.
Roedd Cymru yn lwcus i beidio ildio o leiaf un gôl gynnar ym Mhodgorica pan fethodd Montenegro dau gyfle clir i sgorio.
Vucinic oedd y cyntaf i fod yn wastraffus wrth benio heibio'r postyn o chwe llath yn dilyn croesiad Savo Pavicevic o'r asgell dde.
Ac yna daeth Hennessey i'r adwy wrth arbed ergyd wan Branko Boskovic o du fewn y cwrt cosbi.
Roedd Hennessey eisoes wedi gorfod cynhesu ei ddwylo wedi pum munud wrth arbed ergyd Radomir Djalovic yn dilyn llithriad Ricketts.
Mewn moment brin o ymosod, llwyddodd Bale i gyrraedd y llinell gôl a thynnu'r bêl yn beryglus ar draws wyneb y gôl ond doedd neb yno i fanteisio.
Ond o hynny ymlaen, Montenegro oedd yn rheoli'r chwarae tan ddiwedd yr hanner cyntaf a daeth y gôl haeddiannol wedi 30 munud.
Aeth Vucinic heibio dacl wan Collins i lawr y chwith, gan agor llwybr clir at y gôl.
Roedd yr ongl yn dynn wrth iddo agosáu at y llinell gwsg, ond llwyddodd i wasgu ei ergyd rhwng y postyn cyntaf a Hennessey wrth i'r golwr ragweld croesiad isel.
Pum munud cyn diwedd yr hanner, aeth Bale heibio dau chwaraewr lawr y chwith ac roedd angen blaen troed Boskovic i rwystro'r bêl rhag cyrraedd Craig Bellamy.
Adlamodd y bêl at gapten Cymru, ond aeth ei ergyd droed chwith ym mhell heibio'r postyn.
Ac eiliadau cyn yr egwyl, cafodd Ricketts ei ddal yn cysgu unwaith eto lawr y dde, ac roedd Cymru yn lwcus i weld ergyd Vucinic yn mynd drwy goesau Collins a heibio'r postyn.
Roedd Montenegro yn lwcus i beidio colli dyn ar gychwyn yr ail hanner wrth i Miodrag Dzudovic rwystro Steve Morison ychydig tu allan i'r cwrt cosbi gyda thacl oedd yn fwy addas ar gyfer cae rygbi na chae pêl-droed.
Cerdyn melyn oedd penderfyniad y dyfarnwr, ac aeth ymgais Bale o'r gic rydd heibio'r postyn
Llwyddodd Cymru i oroesi wrth amddiffyn pedwar cic gornel yn olynol wrth i'r gêm gyrraedd yr hanner awr olaf, ac yna gwthiodd y golwr cartref y bêl dros y bar ar ôl i Williams gael blaen troed yn dilyn cornel brin i Gymru.
Roedd Dzudovic yn lwcus eto i aros ar y cae wrth ddal Collins yn ei wyneb gyda'i benelin.
Doedd dim hyd yn oed cic rydd i Gymru, er i'r amddiffynnwr dreulio sawl munud ar wysg ei gefn mewn poen, cyn gorfod gadael y chwarae.
Roedd 84 munud ar y cloc cyn i Mladen Bozovic wneud ei arbediad o bwys cyntaf wrth rwystro ergyd Bellamy yn isel ar ei bostyn agosaf.
Ac o'r gic gornel a ddilynodd, peniodd y capten yn syth at ddwylo'r golwr.
Roedd hi'n ddiweddglo llawn cyffro wrth i Gymru daflu chwaraewr i fyny'r cae, ac roedd hi'n ymddangos fel bod yr ymwelwyr wedi cipio pwynt pan rwydodd Church ar ôl i ergyd Robert Earnshaw adlamu o ddwylo Bozovic.
Ond roedd y llumanwr yn llygaid ei le wrth godi ei luman am gamsefyll a llwyddodd Montenegro i oroesi tan y chwiban olaf a sicrhau buddugoliaeth agoriadol.
Montenegro: Mladen Bozovic, Zverotic, Djudovic, Pavicevic, Jovanovic, Basa, Vukcevic (Beciraj 87), Boskovic (Vladimir Bozovic 73), Pekovic, Vucinic,
Djalovic (Novakovic 83).
Eilyddion: Blazic, Batak, Savic, Delibasic.
Cerdyn melyn: Pavicevic, Djudovic, Pekovic.
Goliau: Vucinic 30.
Cymru: Hennessey, Gunter, Collins (Morgan 75), Williams, Ricketts, Vaughan, Edwards (Earnshaw 68), Ledley, Bale, Bellamy, Morison (Church 78).
Eilyddion: Myhill, Evans, King, Cotterill.
Cerdyn: Morison, Ricketts, Bale.
Torf: 9,862
Dyfarnwr: Anastassios Kakos (Groeg).
