 The date of foundation of the first religious building on this site is unknown. A church was recorded here in the Norwich Taxation of 1254, and the church was owned by the Augustinian priory at Penmon, at the south-eastern corner of Anglesey, during the 13th century; the priory also owned (and therefore received the tithes from) the Anglesey churches of Llanddona and St Cwyllog, Llangwyllog at this time. The current building has medieval walls, and the doorway of the porch on the north side of the church, which is of 15th-century style, is the oldest dateable part of the building. A 2009 guide to the buildings of north-west Wales put the date for the doorway at c.1500. St Mary's was restored in 1867 by Henry Kennedy, the architect of the Diocese of Bangor, after the previous church was struck by lightning. It was funded by Lord Stanley of Alderley, a convert to Islam, whose donations to rural churches carried the requirement that Islamic detail should be included in any restoration work. At St Mary's, the windows have geometric patterns of small panes of coloured glass as a result. This condition was also imposed by him for the restoration work at the nearby church of St Peirio, Rhosbeirio (now closed), where the new windows were also decorated with geometric patterns in glass.
