Mae’n anodd rhoi dyddiad pendant ar bryd codwyd Castell Carndochan ond tybiwyd iddi gael ei hadeiladu yn yr G13 gan Llywelyn ap Iorwerth (Llywelyn Fawr). Er mai dim ond olion o’r castell sydd yn bodoli heddiw, mae adfeilion y tyrrau yn nodweddiadol o’r math o gestyll yr arferai Llywelyn, a’i ŵyr Llywelyn ap Gruffydd, eu hadeiladu.
Mae’r castell yn sefyll ar gopa bryn creigiog rhyw ddwy filltir o bentref Llanuwchllyn ac mae golygfeydd godidog o ardal Y Bala i’w gweld o’i safle.
Roedd hen gwmwd Penllyn, lle safai Carndochan, yn weddol bell o berfeddwlad Gwynedd. Bu tywysogion Gwynedd a Phowys yn straffaglu gyda’r ardal am ganrifoedd. Roedd Carndochan yn strategol bwysig i reoli’r llwybr i mewn i Wynedd, llwybr oedd yn cael ei ddefnyddio gan elynion tywysogion yr ardal yn hanesyddol.
Teithiodd Edward I drwy’r wlad yn 1283–1284 ac mae’n bosib yr ymwelodd â Charndochan, ynghyd â chestyll eraill ar ei ymgyrch. Er hynny, mae’r dystiolaeth ddogfennol yn fud am y castell ei hun. Gwaith archeolegol sydd wedi datgelu rhan helaeth o’i chyfrinachau.
Mae cloddiadau archeolegol ar y safle wedi arwain at sawl canfyddiaeth sy’n rhoi darlun ehangach o hanes Castell Carndochan. Darganfuwyd glain gwydr addurnol wrth y safle sy’n dyddio yn ôl i’r Oes Haearn. Mae’n debygol felly yr amddiffynnwyd safle’r castell yn yr oesoedd cynhanes.