Tua 1113, rhoddodd Arglwydd Normanaidd Caerllion, Robert de Chandos, dir yn Allteuryn i Abaty Bec, ger Rouen yn Ffrainc, a fyddai’n sylfaen i Briordy Benedictaidd Santes Mair Magdalen.
Adeiladwyd y priordy ar ynys ‘Allteuryn’, ardal o dir uchel ar yr arfordir, ac ar y dechrau roedd yn cynnwys tua 200 erw o ‘rostir’ rhwng Allteuryn a Threfonnen.
Mae’n debygol mai morfa heli agored oedd y tir yr adeg yma ac yn borfa garw tymhorol, dim ond yn addas ar gyfer pori yn ystod misoedd sych yr haf, tra bod y llanw yn gorlifo’r tir yn rheolaidd yn ystod y gaeaf.
Er mwyn gwella'r tir, atgyweiriodd y mynachod y morglawdd a’i estyn ar hyd yr arfordir tuag at geg Afon Wysg, ac adeiladu rhwydwaith o ffosydd, neu ‘rhewynau', i reoli lefelau dŵr. Roedd llawer o'r rhewynau yn dilyn nentydd a chilfachau oedd yn bodoli, gan greu patrwm nodweddiadol o gaeau afreolaidd eu siâp a lonydd troellog a welir heddiw. Efallai mai'r mynachod hefyd a fu'n gyfrifol am adeiladu'r Monksditch, y prif rewyn ar ochr orllewinol Whitson.
Erbyn diwedd y 13eg ganrif, roedd rhan fwyaf o'r tir arfordirol uwch yn Allteuryn a Threfonnen yn berchen i’r Priordy, ynghyd â rhannau helaeth o'r ffeniau cefn mewndirol. Roedd hefyd yn berchen ar felinau proffidiol ym Magwyr, Gwndy, St Brides a Milton, a physgodfeydd eog gwerthfawr, gan ei wneud yn gyfoethog dros ben. Bryd hynny, roedd tua 25 o fynachod yn y priordy. Yn anarferol, cofnodir bod y mynachod yn Allteuryn yn gwisgo gwisg wen; roedd mynachod Benedictaidd fel arfer yn gwisgo du.
Dechreuodd ffawd y priordy newid er gwaeth pan ddechreuodd y rhyfel gyda Ffrainc ym 1295. Ystyriwyd Allteuryn fel priordy 'estron' (un oedd ynghlwm wrth fynachlog tramor) a chafodd orchmynion rheolaidd am dâl gan y Goron. Dilynodd trychinebau pellach yn 1324, pan achosodd stormydd garw lifogydd difrifol ar y Gwastadeddau, ac yn 1351, pan gyrhaeddodd y pla. Yn 1334, cyhuddwyd y Prior Phillip Gopillarius, ynghyd â sawl un arall, o ddwyn gwin o longddrylliad oddi ar yr arfordir yn Allteuryn.
Yn 1424, dinistriwyd rhan o adeilad y priordy gan lifogydd a stormydd difrifol, gan gynnwys eglwys y plwyf. Mae'r eglwys blwyf bresennol yn Allteuryn yn dyddio o tua'r cyfnod yma ac mae'n bosib ei bod wedi'i hadeiladu'n rhannol gyda cherrig a gymerwyd o'r priordy (mae rhannau o'r adeilad yn dyddio o'r 12fed ganrif ac mae'n bosib mai ysgubor oedd yn wreiddiol).
Erbyn 1442 roedd y priordy ei drechu a rhoddwyd ei asedau yn gyntaf i Abaty Tewkesbury ac yna i Goleg Eton, un o'r tirfeddianwyr mwyaf ar y Gwastadeddau tan yr 20fed ganrif. Erbyn 1467, peidiodd y priordy â bod. Pan gaeodd y drysau am y tro olaf, dim ond wyth mynach oedd ar ôl.
Ychydig iawn o olion sydd o’r priordy heddiw, er bod awyrluniau o 2010 yn dangos beth allai fod yn sylfeini adeiladau priordy o amgylch Hill Farm. Mae olion parhaol y priordy yn gorwedd yn nhirlun y Gwastadeddau o amgylch Allteuryn a Threfonnen, sy'n dal i ddilyn y patrwm cymhleth o gae a ffosydd a grëwyd gan y mynachod dros 600 mlynedd yn ôl.