Kyrkan i Gammelstad är Norrlands största medeltida kyrka. Den byggdes under 1400-talet och invigdes, enligt traditionen, av ärkebiskop Jacob Ulfsson 1492.
Kyrkan har tillbyggnader för vapenhus och sakristia, spånklätt tak och tegeldekor på gavelröstena. I bogårdsmuren finns två stigluckor, portar, varav den norra är bevarad i ursprungligt skick. I stigluckorna finns igenmurade skottgluggar och i kyrkans östra gavel finns en utsiktslucka. Detta talar för att kyrkan använts som befästning i orostider. Det vitputsade klocktornet byggdes 1851 och ersatte då en äldre klockstapel av trä, belägen nordväst om kyrkogården på bergets högsta punkt.
Kyrkan har en mycket rik interiör och inredning. Korets senmedeltida kalkmålningar är utförda av Albertus Pictors skola. De kalkades över på 1700-talet men togs fram igen 1909. Till höger om altaret finns medeltida korbänkar och en rekonstruerad så kallad biskopsstol.