Potemkin fekete-tengeri flottája a maga idejében hatalmas vállalkozás volt.1787-re a brit nagykövet a vonal huszonhét hajóját jelentette.Oroszországot haditengerészeti alapokra helyezte Spanyolországgal, bár messze elmarad a királyi haditengerészettől.Ez az időszak Oroszország tengeri erejének csúcsát jelentette a többi európai államhoz képest.Potyomkin a területére beköltözött telepesek százezreit is jutalmazta.Becslések szerint 1782-re Novorossija és Azov lakossága megkétszereződött a "kivételesen gyors" fejlődés időszakában.A bevándorlók között voltak oroszok, külföldiek, kozákok és a vitatott zsidók.Bár a bevándorlók nem mindig voltak boldogok új környezetükben, Potyomkin legalább egy alkalommal közvetlenül közbelépett annak érdekében, hogy a családok megkapják a nekik járó jószágot.Novorossziján kívül felállította az Azov-Mozdok védelmi vonalat, erődöket épített Georgievszkben, Sztavropolban és másutt, és biztosította a vonal teljes rendezését.