V enajstem stoletju se je Cerkev odločila na vzhodnem delu oglejskega patriarhata vzpostaviti učinkovitejšo župnijsko mrežo v svojih rokah, saj je bila prej nekako začasna, misijonska in odvisna od volje lokalnih oblastnikov. Na Cerkljanskem je to pomenilo, da bi slednji (po izročilu nasledniki graščaka Brnikarja) morali patriarhu prepustiti odločilno vlogo pri imenovanju župnika, a se očitno niso prostovoljno odrekli starim pravicam pri cerkvi svetega Martina. Na to kaže selitev cerkvenega središča k Marijini cerkvi v bližino vasi Trnovlje, v sedanje Cerklje, pa tudi ljudsko izročilo, ki tedanji graščakinji pripisuje besede, da se raje spremeni v kačo, kot da bi šla v Cerklje k maši. Želja se ji je menda uresničila in še danes pričakuje rojstvo tistega, ki jo bo s tepežem z enoletnimi leskovkami, rešil kačje podobe. Takrat so, na mestu sedanje, gotovo zgradili tudi prvo župnijsko cerkev, ob kateri je nastala vas, ki se po njej imenuje.
V pisnih virih sta bila cerkljanska cerkev in njen župnik, s tem pa posredno tudi župnija, prvič omenjena leta 1154, ali kakšno leto prej. Ker je bila s tem prvič izpričana skupnost na Cerkljanskem, je ta letnica v grbu Občine Cerklje ob treh križih, predstavljajočih tri cerkve, ki naj bi stale v središčnem naselju in naj bi mu, po ljudski razlagi, dale ime.
Župnija je prvotno obsegala vso sedanjo občino Cerklje, torej sedanje župnije Cerklje, Velesovo in Šenturška Gora ter vas Možjanca, ki je od 1937 v župniji Preddvor. Vas Pšata je bila nekdaj enklava župnije Komenda. Razvoj meje med cerkljansko in komendsko župnijo ni dovolj razjasnjen, s tem pa tudi ne nekdanja pripadnost Komendske Dobrave, dela Spodnjega Zaloga in Nasovč. V jožefinski dobi je bila v igri ustanovitev župnije v Zalogu, škof Wolf pa je želel za hribovske vasi cerkljanske fare na Štefanji Gori ustanoviti samostojno župnijo, a načrt ni bil uresničen zaradi pomanjkanja sredstev. Župnija je prvotno sodila v oglejski patriarhat, od 1751 v goriško nadškofijo in od 1787 v ljubljansko (nad)škofijo. V Cerkljah je bil v dveh obdobjih sedež dekanije. Od 1353 do 1782 je bila fara inkorporirana velesovskemu samostanu.
