Croesodd yr asgellwr wedi wyth munud wrth i'r ymwelwyr gychwyn ar dân yn Murrayfield, gyda James Hook yn ychwanegu 11 pwynt arall yn chwarter agoriadol y gêm.
Un gôl gosb ym mhob hanner gan Dan Parks oedd unig lwyddiant yr Albanwyr, er i'r tîm cartref fwynhau sawl cyfnod hir o feddiant.
Seiliwyd y fuddugoliaeth gyda 10 munud i fynd pan gasglodd Williams gic ymlaen gan Jonathan Davies.
Hon oedd buddugoliaeth gyntaf Cymru ers gêm olaf y bencampwriaeth y llynedd, gan godi'r pwysau oddi ar ysgwyddau'r hyfforddwr, Warren Gatland, am y tro.
Penderfyniad Gatland i ddewis Hook yn safle'r maswr ar draul Stephen Jones oedd y prif bwnc trafod cyn y gêm.
Ond profwyd doethineb y dewis yna yn ddigon buan wrth i Hook greu cais cynnar i Williams, gan yna fyna ati i gyfeirio'r chwarae'n feistrolgar.
Roedd ei fylchiad cyn rhyddhau'r asgellwr am y sgôr yn enghraifft berffaith o'i ddawn reddfol wrth redeg, gan achosi anrhefn yn y llinell amddiffynnol.
Ar ôl trosi'r cais cynnar yng nghysgod y pyst, ychwanegodd y maswr tair gôl gosb mewn wyth munud wrth i redeg cryf y Cymry orfodi'r Albanwyr i droseddu yn ei hanner eu hunain.
Roedd Jamie Roberts yn amlwg iawn yn chwarae ymosodol wrth i'r canolwr ateb cri Gatland i fynd i chwilio am y bêl ar bob cyfle.
Ond ar ôl dangos eu dawn ymosodol, profodd yr ymwelwyr bod dycnwch amddiffynnol ac asgwrn cefn yn rhinwedd o'r garfan ar ôl mynd i lawr i 13 dyn.
Cerdyn melyn yr un i Bradley Davies a Lee Byrne o fewn pedwar munud i'w gilydd oedd y rheswm am hynny, ond un gôl gosb gan Parks oedd yr unig bwyntiau a ildwyd.
Dirywiodd safon y gêm o hynny ymlaen, yn rhannol wrth i Gymru ei chael hi'n anodd i gael eu dwylo ar y bêl.
Ond safodd yr amddiffyn yn gadarn unwaith eto, a chynyddodd rhwystredigaeth yr Albanwyr wrth i gamgymeriadau atal llif eu chwarae.
Ar ôl i Parks cau'r bwlch gyda'i ail gôl gosb, cafodd Roberts gyfle euraidd i sgorio ar ôl i'r Alban ildio meddiant yng nghanol cae.
Roedd y ffordd yn glir i'r canolwr at y llinell gais o 40 metr , ond llwyddodd Sean Lamont i'w ddal a'i lorio 10 metr yn fyr.
Serch hynny, cafodd yr Albanwyr eu cosbi am drosedd arall yn fuan wedyn, a tharodd Hook y bêl yn hyderus rhwng y pyst.
Dyna oedd ei gyfraniad olaf cyn ildio ei le i Jones, ond roedd y maswr wedi gwneud hen ddigon i awgrymu mai fo fydd yn cychwyn yn y crys rhif 10 yn y gêm nesaf yn erbyn yr Eidal ymhen bythefnos.
Roedd cyffro a thempo'r gêm yn brysur ddiflannu wrth gyrraedd y 10 munud olaf, ond yna o ddim, sgoriodd Cymru eto i ladd awch yr Albanwyr yn gyfan gwbl.
Manteisio ar gamgymeriad arall y tîm cartref gwnaeth y Cymry, wrth i'r blaenwyr ddwyn y bêl mewn ryc.
Lledwyd y bêl yn gyflym i'r chwith, a gwelodd Jonathan Davies bod cyfle am gic wrth weld aceri o dir gwag o'i flaen.
Doedd hi fawr o syndod i weld Williams yn ennill y ras i'r bêl i sgorio yn ddigon hamddenol, gan ymestyn ei record i 53 cais i'w wlad.
Digon cyfforddus oedd y munudau olaf, ac roedd y rhyddhad yn amlwg ar wynebau'r Cymry wrth allu dathlu buddugoliaeth o'r diwedd wedi sawl canlyniad siomedig.
Yr Alban: Hugo Southwell (Stade Francais), Nikki Walker (Gweilch), Joe Ansbro (Northampton Saints), Nick De Luca (Caeredin), Max Evans (Glasgow Warriors); Dan Parks (Gleision Caerdydd) Rory Lawson (Caerloyw); Allan Jacobsen (Caeredin), Ross Ford (Caeredin), Euan Murray (Northampton Saints), Nathan Hines (Leinster), Alastair Kellock (Glasgow Warriors, capt), John Barclay (Glasgow Warriors), Kelly Brown (Saracens), Richie Vernon (Glasgow Warriors).
Eilyddion: Scott Lawson (Caerloyw), Moray Low (Glasgow Warriors), Scott MacLeod (Caeredin), Ross Rennie (Caeredin), Mike Blair (Caeredin), Ruaridh Jackson (Glasgow Warriors), Sean Lamont (Scarlets).
Cymru: Lee Byrne (Gweilch); Morgan Stoddart (Scarlets), Jamie Roberts (Gleision), Jonathan Davies (Scarlets), Shane Williams (Gweilch); James Hook (Gweilch), Mike Phillips (Gweilch); Paul James (Gweilch), Matthew Rees (Scarlets,capten), Craig Mitchell (Gweilch), Bradley Davies (Gleision), Alun Wyn Jones (Gweilch), Dan Lydiate (Dreigiau), Sam Warburton (Gleision), Ryan Jones (Gweilch).
Eilyddion: Richard Hibbard (Gweilch), John Yapp (Gleision), Jonathan Thomas (Gweilch), Josh Turnbull (Scarlets), Tavis Knoyle (Scarlets), Stephen Jones (Scarlets), Rhys Priestland (Scarlets).
