In September 1739, 12 men were dispatched by Vitus Bering to build a small residency for the officers of the St. Peter and St. Paul, the 2 boats that would take Bering and Chirikov to Alaska. The next year, Navigator Ivan Elagin created the first marine chart of Avacha Bay with the names "Saint Peter" and "Saint Paul." In a letter to Vitus Bering, he described "Petropavlovsk Bay" where the future city would be built. Alexey Chirikov, Bering's partner in the 2nd Kamchatka Expedition of 1741 wrote of "Petropavlovsk" when describing the area.

     After the loss of Vitus Bering due to scurvy on Bering Island, in 1742, Chirikov recommended departing Avacha Bay. September 26, 1743 the order was given to close down the 2nd Kamchatka Expedition. The buildings remaining either fell to ruin or burned.  By the end of the 1770's, the new Kamchatka Commander ordered barracks to be built for 32 soldiers and 2 officers.

     With the expansion of international maritime expeditions, during the late 18th and 19th centuries, Avacha Bay and Petropavlovsk offered safe harbor for the world's most famous mariners. In 1 779 Charles Clark, the leader of Captain James Cook's expedition following Cook's death in Hawaii, visited Petropavlovsk twice. On Clark's second trip, he died and was buried not far from the port.

     Petropavlovsk, because of its location and ample natural harbor, became a vital rest and re-supply port for sea going vessels. The winter population often swelled two­fold as mariners wintered over before setting out again in spring for whaling or commercial cargo hauling. In 1 787 the great French marine explorer Jean-Francios de Galaup La Perouse came to Kamchatka. He visited Clark's grave and ordered the hammering of a copper plaque, honoring Clark. He noted also that the population of the settlement was no more than 100, forty of whom were soldiers. While in Avacha Bay, he accomplished the first documented ascent of Avachinsky Volcano.

     By the beginning of the 19th century the population of Petropavlovsk grew to nearly 180 people year round and winter 300-400 people. Famed marine explorer I. F. Krusenstern visited in 1804, building a fence around the grave area of Charles Clark. To protect the grave from looting or vandals, he closed the gate with a lock and gave the key to the commandant of Petropavlovsk.  In 1827, requests from Kamchatka to the Tsar included support for a Kamchatka library with literature for adults and children. Most houses were surrounded by vegetable and berry gardens.  British sailor Frederick Beechy visited the port in both 1826 and 1827 and wrote in his diary about the governor's garden, with winding gravel paths and monuments to Vitus Bering and Charles Clark.

     Despite the slap-dash huts and houses poorly built of poplar and branches, by 1829 Petropavlovsk's regional report described a seminary, a school, one store, and a library. Two officers' barracks housed most of the military. By 1830 the population has grown to 609 people including the village of Avachinsky. Soon more barracks were built to house the annual winter influx of sailors, hunters, and adventurers who waited on the banks of Avacha Bay for sailing weather.

     The year 1850 brought an influx of 1000 soldiers as the fort at Okhotsk was closed making construction of new housing a critical necessity. That year, the new governor of Kamchatka, V. S. Zavoiko, along with his wife and family arrived in Petropavlovsk where he would serve for the next 5 years. In 1852, engineer K. Ditmar described Petropavlovsk as a small wooden city built along the shores of the bay consisting of 116 homes. The town meandered along 2 parallel roads and wooden bridges crossed 9 streams that rushed out of the hills above the city. By the next year, the local population was reported to be 899 men and 511 women. During the service of Governor Zavoiko, intensive building developed the city with lumber brought south from Nizhne-Kamchatsk.  In 1854, under the leadership of Governor Zavoiko, Petropavlovsk successfully defended Russia's interests in a battle with Anglo-French frigates. With this brilliant victory in the Crimean War, a war which Russia subsequently lost, Governor Zavoiko was promoted in 1855 to General-Governor of Eastern Siberia and transferred from Kamchatka.

     In 1865, American adventurer George Kennan assessed Petropavlovsk as a settlement that couldn't be called "civilized." He described buildings constructed with no aesthetics, a confusing and nonsensical layout of the city's roads and trails, and generally no culture or amenities.

     These must have been very difficult years as the population of the city dwindled to 427 from over 1000, 15 years earlier. This tendency continued into the 1870s with many cabins and homes falling to ruin.  From 1874-1878, Edmund Sandalin, a US citizen, served as the mayor of Petropavlovsk. During his tenure he increased income into the city's treasuries by charging fees for passports and other documents. He retired in 1878 and was awarded a silver medal for his service. Petropavlovsk continued to resemble a backwater hovel and one visitor I. Serebryanikov described it: "The ruined appearance and the number of inhabitants likens Petropavlovsk to a small, poorly built little village." General Lieutenant M. M. Dukhovsky of the Priamursky Region visited Petropavlovsk in 1897 and was shocked at what he found commenting, " I with deep regret look at the picture of ruin and abandonment, that Petropavlovsk now presents; this port, with its incredible bay, former regional center, with its own history of the great and memorable days of 20-24 August, 1854-Petropavlovsk battle."

     In 1918, famed explorer V. K. Arsenyev wrote of Petropavlovsk, "Petropavlovsk has the look of a village and reminds one of the Klondike. All of the buildings are wooden. One street and one sidewalk.  From the hills rush bubbling streams with clean, cold water.  Near the houses are small gardens. Some houses built long ago were from ship's timbers..." When the Soviet powers took over, one of the first tasks of the new governor was to name the streets with patriotic names like Leninskaya, Tamozhennaya, Partizanskaya, Krasnaya, Sovetskaya, in an effort to bring some order to the city's helter-skelter organization.  In 1924 the Soviet leadership declared Petropavlovsk-Kamchatsky to be the main seat of government for the Kamchatka Peninsula.