Taganrog was born as the first Russian Navy base and the biggest fortress in South of Russia. Construction of the fortress on the coast of the Azov Sea was aimed at improvement of Russian political, military and strategic situation as it struggled for the access to open seas. The establishment of Russia as a sea power began from the resolution of the “Turkish Problem” – the fight for the Azov Sea.

In January 1695 the preparations for the war against the Ottoman Empire were started. The siege of Azov started on July 8, 1695. The army comprised crack regiments and the Don Cossacks and was divided into three units under the command of François Lefort, Patrick Gordon and Avtonom Golovin. Another Russian army (120,000 men, mostly cavalrymen, Streltsy and Cossacks) under the command of Boris Sheremetev set out for the lower reaches of the Dnieper with the goal of diverting the Crimean Khanate's attention. Between June 27 and July 5, the Russians completely blocked Azov from land. After two unsuccessful attacks on August 5 and September 25, the siege was lifted. The failure of the first siege attempt highlighted the significance of having a war fleet and marked the beginning of Russia's turning into a maritime power.

By order of Peter the Great was started the construction of the Russian Navy. On April 23, 1696 the Azov Flotilla set out for its first campaign, while the main forces (75,000 men) under the command of Aleksei Shein started to advance towards Azov by land and by water (the rivers of Voronezh and Don). Peter I and his galley fleet left for Azov on May 3. On May 27, the Russian fleet (2 battleships - “Apostle Paul” and “Apostle Peter”, 4 fire ships, 23 galleys, 100 rafts etc.) under the command of Lefort reached the sea and blocked Azov. Russian fleet insured the naval blockade of Azov. On June 14, the Turkish fleet (23 ships with 4,000 men) appeared at the mouth of the Don. However, it left after losing 2 ships in combat. After massive bombardment from land and sea and seizure of the external rampart of the fortress by the Cossacks on July 17, the Azov garrison surrendered on July 18.

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 Fyodor 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.

To insure Russian positions in the South, and to shelter the Russian Navy, Peter the Great needed a new haven for the fleet, and a fortress to protect it. Azov could not serve as naval base because of shallow waters of the river Don. That is why, a few days after Turkish capitulation, on July 27, 1696 the Russian tsar set out for an expedition to explore the coastline of Azov Sea. The expedition stopped at the cape Tagan-Rog on July 27, where Peter the Great spent the night of July 27-28, 1696. The cape was selected as the perfect place for the harbor, since the sea around the cape was deep enough for sea boats; there was enough room for a haven with solid stone soil; and the expedition found a small water spring.

The first Russian Navy base, Taganrog was officially founded by Peter The Great on September 12, 1698. Taganrog is one of the first Russian cities, which was built according to a pre-established detailed plan. Vice-Admiral Cornelis Cruys, who is regarded as the architect of the Russian Navy, became the first Head of Taganrog city 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 1698, basing on the instructions provided by Peter the Great. 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 8,000 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 Boris Sheremetev were surrounded by superior Turkish forces near Prut River. The Russian tsar had to sign a treaty stipulating the return of Azov to Turkey and destruction of 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 born again thanks to Catherine the Great, who issued a decree addressed to the Vice-Admiral Aleksey Senyavin. Taganrog once again became the base of the Azov Flotilla.

April 8, 1783 the Crimea was annexed by Russian Empire and the fortress of Taganrog lost its importance. The Azov Flotilla became the starting point in creation of the Russian Black Sea Navy. February 10, 1784 Catherine the Great issued a decree abolishing Taganrog’s fortress status, and thus Taganrog transformed into a noisy commercial seaport.

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 also by generous civic arts, founding orchestras, clubs, schools and churches, bringing in French chefs and importing Italian sculptors.