The church in Käina was erected in the years 1492-1515, during the reign of Ösel–Wiek bishop John III Orges, as one of the youngest, Gothic temples of the West Estonian archipelago. It was created on the site of an earlier church 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 built as a simple, aisleless building with a narrower four-sided chancel on the eastern side, opened to the nave with an ogival arcade. Later, a slender, four-sided tower was added on the west side.