Shelekhov organized voyages of merchant ships to the Kuril Islands and the Aleutian Islands starting from 1775. In 1783–1786, he led an expedition to the shores of what is now known as Alaska, during which they founded the first permanent Russian settlements in North America. Shelekhov's voyage was done under the auspices of the Shelikhov-Golikov Company, the other owner of which was Ivan Larionovich Golikov. This company was the basis for the Russian-American Company, which was founded 1799.
In 1784, Shelekhov arrived in Three Saints Bay on Kodiak Island with two ships, the Three Hierarchs, Basil the Great, Gregory the Theologian and John Chrysostom and the St. Simon. The indigenous Koniaga, an Alutiiq nation of Alaska Natives, defended themselves from the Russian party. In what became known as the Awa'uq Massacre, Shelekhov and his forces killed hundreds, including women and children, and took hostages to threaten the safety of the other Alaska Natives. Having established his authority on Kodiak Island, Shelekhov founded the first permanent Russian settlement in Alaska on the island's Three Saints Bay. (Unalaska had been established long before, but it was never considered the permanent base for Russians until Shelekhov’s time).
A gulf in the Sea of Okhotsk, a strait between Alaska and Kodiak Island, and a town in Irkutsk Oblast in Russia bear Shelekhov's name. Shelekhov travelled via Shelekhov Bay in the Sea of Okhotsk in December 1786-January 1787, after he had been left behind at Bol’shereck in Kamchatka as the winds tore the Three Hierarcs from her anchors and carried her out to sea. There is a statue of Shelekhov in his native Rylsk.
In 1775 Shelekhov married Natalia Alexeyevna Kozhevina, the daughter of a prominent clan of Okhotsk navigators and mapmakers and their wives. At his death he had five surviving daughters and one son.