Peter the Great tried to conquer the Turkish fortress of Azov to get an entrance to the Sea of Azov and the Black Sea. His first campaign against Azov in 1695 failed, but his second attempt the next year led to victory. To keep Azov in his possession and hold off the Turkish Navy, the tsar ordered to expand his small war fleet built during the winter of 1695-96. Peter the Great put the Azov Fleet under the command of admiral F.A. Golovin, a Russian nobleman who was the successor of the Swiss François Lefort. Golovin was assisted by vice-admiral Cornelis Cruys and rear-admiral Jan van Rees.

The first Russian Navy base, Taganrog was officially founded by Peter I The Great on September 12, 1698. Taganrog is one of the first Russian cities, which was built according to a detailed plan. Vice-Admiral Cornelis Cruys, who is regarded as the architect of the Russian Navy, became the first Head of Taganrog Fortress in 1698-1702 and in 1711, and produced the first maps of Azov Sea and Don River. The project for planning and building works in the city was established in 1699, basing on the instructions provided by Peter The Great.

In 1704 the ploughing of virgin lands started. Next year were planted the imperial vineyard and orchards. The building and construction of the seaport, fortress and town were generally completed by the end of the first decade of the 18th century. The seaport of Taganrog represented an irregular water surface of some 774000 square meters; it was the first artificial seaport in Russia. The pentagonal fortress was erected on the Cape. Inside the fortress were built stone living-quarters for soldiers and civil population.

By the middle of 1711, according to the information of Mandating Chamber of Taganrog, there were over 8000 inhabitants in Taganrog. As the development of the social life in the region progressed, Taganrog retained its military and administrative significance and gradually became the handicraft and commerce center.

In 1700-1711, the Azov Sea Navy was the guardian of Russia's Southern frontiers. But in 1710 Turkey unleashed a new war against Russia. Russian troops commanded by Peter the Great were surrounded by superior Turkish forces near Prut River. The Russian tsar had to sign a treaty returning Azov to Turkey and destroying Taganrog. On September 19, 1711 by the order of Peter the Great, Taganrog was demolished and in February 1712 Russian troops left the town. For fifty years the seaport, fortress and town laid in ruins.

The Turks recaptured it twice (1712 and 1739), but it was taken by the Russians in 1769 and definitively ceded by Turkey in the Treaty of Kuchuk Kainarji (1774). On April 2, 1769 Russian troops entered Taganrog. The city was refounded by Catherine the Great, who issued a decree addressed to the Admiral A.N. Senyavin. Taganrog was populated by Greek colonists who, like the Greeks of classical times, took refuge from poverty or tyranny in townships around the northern Black Sea and the Sea of Azov. Some Greeks had been Mediterranean pirates and were now tycoons; many lived by cheating Russian farmers and bribing Russian customs officials. They spread wealth, not only by conspicuous consumption, but by generous civic arts, founding orchestras, clubs, schools and churches, bringing in French chefs and importing Italian sculptors. In Chekhov's boyhood, they were followed by Italian and Russian merchants, and by dealers of all nations, exploiting the wealth of Taganrog's awakening hinterland. The city developed feverishly.