Псковские летописи сообщают под 1542 г. о построении в городе Острове храма. Никольский храм был патрональным и соборным до 1790 года, до тех пор, пока не был построен Троицкий Собор. На барабане церкви сохранилась храмозданная керамическая надпись, подтверждающая дату постройки церкви. Одновременно перечисляются строители храма.

Первое описание церкви относится к 1764 году. «Каменная, крытая тесом, на ней глава обита жестью, крест железной рогатной позлаженной. На колокольне два больших и два маленьких колокола, совсем обветшала». В 1801 году построена двухъярусная колокольня над притвором. Материал стен – известковая плита.