Pavlov qalasının təməlləri hələ 1697-ci ildə Azov dənizi sahillərində yerləşən Petruşin dili ərazisində qoyulmuşdu. Tikinti işləri avstriyalı mühəndis Antoni Yakovleviç Lavala həvalə edilmişdi. 1698-ci ilin martında tikinti işləri tamamən dayandırılmışdır. 1701-ci ildə isə tikinti işləri bərpa edilir. Ancaq qala əvvəlki ərazidə inşa edilmir. Onun tikinti yeri Miusski dilini limanının hissəsinə köçürülür. Qalanın yaxınlığında Qaevka adlı yaşayış məntəqəsi yerləşirdi.

Bu tikili Rusiyada dəqiq mühəndis-riyazi metodlardan istifadə edilərək layihələndirilmişdir. Tikili dörd künclü formaya malik olaraq 237-nin 80 olmuşdur. Bir meddət sonra bu tip qalalar Rusiyanın digər ərazilərində belə inşa edilmişdir. Bunlara misal kimi Sankt-Peterburqda Petrovavlovski qalası, Staroçekasskidə Anna qalası və Rostov-na-Donu şəhərində isə Müqəddəs Dmitri Rostovski qalasını göstərmək olar.

Pavlovski qalası Petovski retranşmentinin qərb qutaracağını təşkil edirdi. Qalaya 500 nəfərlik qarnizon sərbəst şəkildə yerləşə bilirdi. ikinci müdafiə xəttini təşkil edirdi. Ərazini çöl sahəsi hissədən qoruyurdu. Qalanin bir hissəsi 1711-ci ildə Osmanlı imperiyası ilə Rusiya imperiyası arasında imzalanmış Prut sülh müqaviləsinə əsasən dağıdılmışdır.

1736-cı ildə Pavlovski qalasında Pyotr Petroviç Lassinin qoşunları yerləşdirilmişdi.

Qalanın qalıqlarını bu günümüzdə belə Qaevka kəndi yaxınlığında müşahidə etmək mümkündür.