Förutom sakristian från 1700-talet så är Östergarns kyrka byggd i mitten av 1200-talet. Kyrkan har inget torn utan en så kallad takryttare, men spår i muren avslöjar att man hade planer på att bygga ett torn. Av den ursprungliga medeltida kyrkan finns inte mycket mer än kyrkans murar bevarade då kyrkan flera gången varit utsatt för krigshandlingar.
År 1565 under Nordiska sjuårskriget brändes kyrkan av svenska trupper, och all medeltida inredning förstördes eller rövades bort. Under det Stora nordiska kriget plundrades kyrkan två gånger, 1715 och 1717, av ryska styrkor. Efter det fick kyrkan förfalla i några år innan det under kyrkoherde Lars Nilsson Neogards tid reparerades och förnyades mellan 1725-1758.
Mer än i andra kyrkor på Gotland har det sena 1900-talet och 2000-talet, fått var med. Olika konstnärer har under de senaste decennierna bidragit med ett antal verk. Det första tillägget skedde med anledning av att de sönderbrända delarna i södra långhusportalen ersattes med ny sten 1978, där Bertil Nyström och Henna Karlsson formgivit de nya kapitälbandens reliefer.