Innocent, whose secular name was John Veniaminov, was born in 1797 in the village of Anginskoye, Verkholensk District, in the Irkutsk province of Russia.

In 1823, Michael, the Bishop of Irkutsk, was instructed by the Holy Synod to send a priest to the island of Unalaska in the Aleutians. Following only two years of service as a parish priest, John Veniaminov volunteered for the mission to the Aleutian islands. In May of 1823, John, his wife, his infant son, and his brother Stefan set forth on their long and arduous journey, which took more than a year.