В 1836 году на острове вспыхнула эпидемия оспы, унесшая жизни едва ли не половины туземцев. Русских же эпидемия почти не коснулась, ибо к тому времени врачи научились побеждать болезнь с помощью прививок. Это обстоятельство заставило колошей с большим вниманием отнестись к опыту европейцев. Отец Иоанн помогал врачу компании бороться с болезнью и сумел приобрести доверие и авторитет среди индейцев.

Однако прежде чем начинать среди них проповедь христианства, он должен был изучить их обычаи, традиционные верования и, главное, язык. Лишь спустя три года миссионер приступил к проповеди Евангелия. Ему приходилось совершать службу под открытым небом, за отсутствием подходящей церкви. К пастве проповедник обращался на ее родном языке.

Деятельность миссионеров в Русской Америке протекала в чрезвычайно тяжелых условиях. Население разбросано на огромных пространствах, священников всего четверо, мизерное жалование не позволяло вести мало-мальски сносную жизнь. К тому же по всем вопросам приходилось сноситься с епархиальными властями в Иркутске, находившемся за тысячу верст. В ноябре 1838 года Иван Вениаминов отправляется в Петербург. (Вместе с собой он взял свою семилетнюю дочь Феклу. Супруга же с четырьмя детьми отправилась в Иркутск, где учились старшие сыновья.) Вениаминов решил представить на рассмотрение Священного Синода подготовленный им проект улучшения миссионерской деятельности в Русской Америке, а также организовать сбор средств в пользу американской церкви. Кроме того, отец Иоанн хотел добиться разрешения на печатание на алеутском языке Священного писания. Архиепископ Иркутский Нил, сам прославившийся миссионерской деятельностью среди забайкальских бурятов, дал ему свое благословение. С разрешения Российско-Американской компании Вениаминов морским путем отправился к берегам России вокруг Южной Америки и через семь с половиной месяцев, 25 июня 1839 года, достиг Петербурга.

Здесь он встретил весьма благожелательный прием. Его сообщение об Алеутских островах и Аляске вызвали большой интерес не только в Синоде, но и в научных кругах, в которых имя священника Ивана Вениаминова было уже хорошо известно. За годы своего пребывания в Русской Америке миссионер собрал множество сведений самого разного характера, представляющих интерес для этнографов, историков, географов, ботаников, геологов. Сам император Николай I уделил ему внимание. Святейший Синод даровал отцу Иоанну сан протоиерея.

Отец Иоанн предоставил в Синод доклад «Обозрение Православной Церкви в российских поселениях в Америке, со своим мнением об улучшении состояния оной». Представители Синода обещали ему поддержку, но не ранее осени. В ожидании решения Вениаминов отправился в Москву для сбора средств, необходимых для построения храмов в Русской Америке. Здесь произошла его встреча с митрополитом Московским Филаретом (Дроздовым), одним из крупнейших деятелей церкви того времени (впоследствии причтен Церковью к лику святых). Святитель Филарет горячо поддержал отца Иоанна и даже предоставил ему свою квартиру. К осени 1839 года Вениаминову удалось собрать немало средств, а также церковной утвари и священнических облачений, необходимых для церковной службы.