Desconhece-se o ano da sua construção, sabendo-se apenas que é anterior ao século XVI. E sabe-se que é anterior ao século XVI, dado existir na Biblioteca Pública de Braga, uma «Relação de todas as Igrejas do Arcebispado e seus Padroeiros», onde consta, para além de outras 26 igrejas da região de Barroso, a «Igreja de colação do Arcebispo de Santa Maria de Gralhas».Embora tratando-se de um documento sem data, pela caligrafia e ortografia, verifica-se ter sido manuscrito, no início do século XVI, razão pela qual, a Igreja terá sido construída no antecedente.A esta aldeia e à sua Igreja, se refere também o respectivo Vigário, Francisco Affonso dos Santos, que sob o testemunho do Vigário de Santo André de Vilar de Perdizes, Agostinho Alvares e do Reitor de São Miguel de Vilar de Perdizes, Miguel do Couto de Oliveira, quando em 20 de Março de 1758 e em resposta a uma ordem emanada do Muto Reverendo Senhor Doutor Vigário Geral, para que lhe desse conta do que havia nesta freguesia, lhe respondeu o seguinte:

Esta freguezia de Santa Maria de Gralhas está sita na província de Trás dos Montes no Arcebispo de Braga Primaz, da comarca de Chaves, eclesiástica e do secular de Bragança e o hé do termo da vila de Monteallegre. Hé freguezia matriz.