14 октября 1896 г. Иустин был назначен епископом Уфимским и Мензелинским, 14 ноября прибыл в Уфу. Как и в Тобольске, одним из первых его деяний на новой кафедре стало учреждение епархиального братства в честь Воскресения Христова при кафедральном соборе, торжественное открытие которого состоялось 20 декабря того же года. Согласно уставу, братство действовало под председательством правящего архиерея, имело миссионерский, просветительный, попечительный и распорядительный отделы. С помощью братства Иустину удалось добиться существенных результатов в устроении различных сторон епархиальной жизни. Так, братство учредило должности епархиального и уездных противораскольнических и противосектантских миссионеров, содержало кафедру истории и обличения «мухаммеданства» в Уфимской духовной семинарии, организовывало миссионерские беседы. Также братство собирало точные статистические сведения по епархии о числе раскольников, сектантов и иноверцев. На средства братства издавалась и распространялась духовно-просветительная литература. За вечерними богослужениями в крестовой Свято-Духовской церкви, а также во время поездок по епархии Иустин бесплатно раздал до 300 тыс. экз. книг и брошюр религиозно-нравственного содержания. В 1897 г. братство открыло книжную лавку и епархиальный книжный склад с целью распространения среди прихожан брошюр религиозно-нравственного и церковно-исторического содержания, образков и крестиков, что способствовало созданию новых и пополнению старых фондов приходских библиотек. В 1897 г. при Казанском соборе города Стерлитамака братство создало противораскольническую библиотеку. 1 октября 1897 г. братство открыло в Уфе трёхгодичный класс подготовки псаломщиков по составленной Иустином программе «Общего обучения в псаломщицком классе». К 1 января 1899 г. в этом классе обучалось 28 учеников, из которых 22 происходили из духовного сословия, а шесть – из других сословий; 13 учащихся были сиротами или из бедных семей и пользовались содержанием от братства. Определением Совета братства от 6 октября 1898 г. третий год обучения в классе предназначался для изучения предметов по программе двухклассных церковно-приходских школ с добавлением предметов, положенных в особых «Правилах для производства испытаний по духовному ведомству на звание учителя одноклассной церковноприходской школы». Это давало возможность способным учащимся после сдачи экзамена поступать учителями в церковноприходские школы и школы грамоты. Иустин принимал энергичные меры по увеличению количества церквей, попечительств при них и приходских школ. Вскоре после прибытия на кафедру освятил после реконструкции Петропавловскую церковь тюремного замка, а также утвердил кандидатуры священника и псаломщика, которым надлежало совершать службы в воскресные и праздничные дни и заботиться о духовно-нравственных нуждах заключённых.