The church in Käina was erected in the years 1492-1515, during the reign of Ösel–Wiek bishop John III Orges, which is considered to be one of the youngest, gothic temples of the West Estonian archipelago. It was created on the site of an earlier temple from the 13th century. Initially, the patron of the church was Saint Nicholas, but later the call was changed to Saint Martin. In the sixties of the seventeenth century, the eastern wall of the church was supported by powerful buttresses to prevent damages, caused by building subsidence. In the years 1859-1860, the church was thoroughly rebuilt. The southern wall of the nave was dismantled, and the nave was expanded with a new, large structure in the southern part of the building. In 1941, the church was hit by an incendiary missile which, bursting through the choir ceiling, completely burned the building. From that moment, the building is in ruin, although its reconstruction is planned.
The church was created as a simple, aisleless, single-nave building with a narrower, quadrangular chancel. Later, a tower on the west side was added.