Kristendomen kom troligen till bygden redan på 1000-talet, och man kan anta att det tidigt fanns en träkyrka på platsen. Redan 1100-1200 byggdes de äldsta delarna av Gryta kyrka. Äldst är långhuset.
Under 1400-talet byggdes kyrkan om och till, med torn, vapenhus och sakristia. Av tornet finns idag endast den nedre delen kvar i kyrkans västra del. Under 1400-talet ersattes ofta platta trätak med höga tegelvalv - vackert och också skydd mot elden. Valven tillkom vid olika tidpunkter under om- och tillbygnadsarbetet och har olika form: enkla kryssvalv, mer komplicerade åttadelade kryssvalv och i det tidigare tornet ett stjärnvalv.
När tegelvalven byggdes fick de också de vackra målningarna som präglas Gryta kyrka. Målningarna kan tack vare en tydligt inskrift dateras till Marias dag 1487. De är i den stil som Albertus Pictor gjorde uppskattad och känd, och troligt är att målningarna i Gryta kyrka utfördes av en av hans lärjungar.
Kyrkan byggdes delvis om efter en häftig brand 1578. Enligt traditionen fick kyrkan stöd för återuppbyggnaden från kung Johan III och renoveringen kunde avslutas redan 1581. Troligen byggdes koret samtidigt om enligt tidens ideal så att det fick den halvrundade form vi ser idag.
Från sekelskiftet 1700 och det följande århundradet tillkommer bland annat predikstol (1697, troligen gjord av en lokal snickare) och altaruppsatsen (1752, av bildhuggaren Olof Gerdman, Stockholm). Under det sena 1700-talet fortsätter renoveringen: den övre delen av tornet tas bort, nya fönster öppnas för att ge mer ljus och alla valven målas vita. Först vid en restaurering 1929-30 tas de vackra takmålningarna fram igen, till glädje för nya generationer.
Vid kyrkogårdens bortersta kant står klockstapeln från 1752.