Volgens een legende werd de kerk van Grammene gesticht samen met de kerk van Gottem door twee zusters die het niet eens konden worden over een plaats voor de kerk. De ene werd 'gram' en stichtte Grammene, de andere Gottem. Dit Sint-Martinuskerkje van Gottem heeft een gelijkaardige inplanting aan de Leie, een gelijkaardige toren (eveneens beschermd) en een gelijklopende geschiedenis. In archiefdocumenten vinden we een eerste vermelding van de kerk van 'Grimmine' in 1121, namelijk bij de schenking door de bisschop van Doornik van het patronaatsrecht van de kerk aan de Gentse Sint-Baafsabdij. Het toponiem 'Grimmine' is geëvolueerd uit het oud Germaanse 'grimminja' of grimmige nederzetting.

F. De Potter beschrijft in de jaren 1860 de kerk als "een eenbeukige kruiskerk, voornamelijk gewijzigd in de 16de en de 18de eeuw, met een van 1762 daterend gewelf en een achthoekige toren met spits boven de voorgevel, dus als westtoren doch vermoedelijk in oorsprong een kruisingstoren". Begin 20ste eeuw was de kerk nog witgekalkt. In 1902 vraagt de pastoor hulp daar de zeer oude kerk dreigt in te storten na vernieling door vandalen. Enkel de achthoekige bakstenen toren op zware vierkante basis, bleef behouden en werd geïntegreerd in een nieuwe neogotische kerk. Deze toren is vermoedelijk circa 1300 te dateren en werd begin 17de eeuw verhoogd na brandstichting door hervormers in 1592. Een 1609 gedateerde balk binnenin verwijst naar de heroprichting.