Построена в 1835 году для обороны от набегов кочевников.
Находится в селе Николаевка Варненского района, в 82 км на юго-восток от Варны.
Когда заезжаешь в Николаевку, то сначала издалека маячит зеленый купол церкви Святителя Николая. Но по мере приближения вырастает белая стена. Она становится все больше и больше, все ближе и ближе.
И вот, наконец, перед вами во всей красе встает казачья крепость, построенная в 1835 году для обороны от набегов кочевников. Сторожевое укрепление в Новолинейном районе Оренбургского казачьего войска. Крепость была заложена в день памяти Святителя и Чудотворца Николая. Отсюда название крепости и села.
Укрепление построено в форме квадрата 70 х 70 м с зубчатыми стенами высотою 12 м и толщиной полметра. По углам четыре башни с бойницами для пушек. С внутренней стороны к стенам примыкал земляной вал по всему периметру. Сейчас этот вал не сохранился.
Через 10 лет, в 1845 году в центре бастиона появился храм Николая Чудотворца. Здание высотою 17 м пятикупольное. В центре – главный купол, а четыре маленькие главки расположены по частям света. Западная главка больше других. Это колокольня.
Здание крестообразное в основании, сложено из кирпича, который изготавливали на месте. Кирпичи имеют необычную, плоскую и длинную форму.
В 40-е годы XIX столетия крепость неоднократно подвергалась нападению кочевников, но смогла устоять. Степняки не умели вести длительную осаду. Их сила была в другом: в количестве воинов и в неожиданности и быстроте натиска. Поэтому кирпичные высокие стены представляли для них серьезное препятствие. Свое назначение бастион всегда выполнял.
Крепость время тоже не пощадило. Из всех сооружений остался один храм. Он реставрируется, но является действующим.
В 1971 году постановлением облисполкома фортификационное сооружение признано памятником истории и архитектуры местного значения. Взято под охрану государства.
В 1990-е годы храм реставрирован. При реставрации помогали местные школьники с учительницей. По их сведениям, стены к тому времени до половины были занесены землей.
Через шесть лет после реставрации по решению Министерства культуры РФ и Комитета по управлению государственным имуществом храм и крепость были переданы в безвозмездное и бессрочное владение Челябинской епархии РПЦ. В настоящее время храм действующий.