Вдохновляющим активность духовенства фактором стало требование владыки об участии клира в миссионерских организациях: Обществе св. Гурия в Казани, Православном палестинском обществе, Восточно-русском культурно-просветительном обществе в Уфе, задачами которых было распространение православия среди мусульман и язычников и укрепление благочестия в православных общинах. Миссионерская деятельность, которой владыка посвятил себя с самого начала пастырского служения, вообще занимала значительное место в его жизни. Как личность он пользовался уважением и авторитетом среди иноверцев и своими проповедями достигал большого успеха в деле распространения православия в их среде. За сравнительно короткие сроки его усилиями были созданы Трехсвятительский крещено-татарский мужской скит и Покровская крещено-татарская женская община [88] , открыты многочисленные приходы. Свое обращение к православию неофиты связывали с личностью еп. Андрея – для них он был воплощением христианского подвижничества. «Он один из архиереев отстаивал национальные интересы загнанных народностей – чуваш, черемис, вотяков и т.д. Он был и есть любимец низшего, бедного, загнанного люда. Казань и Уфа, где он служил, в самых бедных слоях населения помнят его добрую, ласковую, отзывчивую душу; беженцы Западного края одеты были только им», – напоминал новым властям в 1924 году знавший владыку по Казани протоиерей Транквиллин Земляницкий [89] .
Владыка уделял особое внимание новокрещеным приходам, до мелочей разрабатывал рекомендации их наставникам, способствовал широкой публикации богослужебной литературы на языках народов Урала и Поволжья. Особенно настойчиво он требовал, чтобы храмовая служба велась на языке большинства прихожан или, по меньшей мере, «на двух языках попеременно» [90] . Примечательно, что соответствующее распоряжение было одним из первых актов владыки по вступлении его на уфимскую кафедру. Позднее, на заседании шестого отдела Предсоборного совета «по вопросу о допущении малорусского, русского и других народных языков в богослужение», состоявшемся 10 июля 1917 года, «Андрей, еп. Уфимский, указал на большую религиозность татар, которая объясняется имеющимся у них татарским текстом некоторых церковных книг, добавив, что
Замечательным фактом архипастырского служения было глубокое преобразование церковно-общественной жизни Сухумской епархии, проведенное еп. Андреем за два с небольшим года. Сразу же после своего появления там он, в частности, создал первый молитвенный дом в селе Псху, после революции почти 15 лет служившем главным оплотом монахов-имяславцев [92] . В антирелигиозной литературе об этом повествовалось так: «…В 1911 году первый поп, который пробрался на Псху, был епископ Андрей или, иначе, князь Андрей Ухтомский. Был, говорят, большой ханжа и замечательный оратор. Закатывал псхусцам сногсшибательные проповеди о спасении души человеческой… и основал, впервые на Псху, очаг спасения заблудших грешников. Сейчас князь Андрей в каком-то ленинградском учреждении, на правах равноправного гражданина и советского служащего, исчисляет статистические таблицы» [93] .
Важнейшим проводником своих идей владыка считал печатное слово. Количество его статей и выступлений в светской и церковной прессе исчисляется многими сотнями, а географически – они издавались почти по всей стране. Немало и отдельно изданных книг, брошюр и оттисков статей. Еп. Андрей основал первый церковный орган в Сухумской епархии – «Сотрудник Закавказской миссии» (1912–1916), его детищами были также газета «Дус» (на татарском языке в русской транскрипции), казанский еженедельник «Сотрудник Братства святителя Гурия» (1909–1911), «Заволжский летописец» в Уфе.
Многочисленные отзывы о деятельности владыки в Казани, Сухуми, Уфе говорят о любви и уважении, которыми он пользовался в самых различных слоях как русского, так и инородческого православного населения. Даже в конце 1920-х в одной из своих повестей бывший уфимец, писатель Борис Четвериков не без теплоты и сочувствия вспоминает об еп. Андрее. Школьный инспектор своими придирками довел гимназиста до самоубийства; общественность взволнована и возмущена, но встал вопрос, где хоронить юношу: по строгим правилам – только вне ограды кладбища. Губернатор отправился к владыке: