Одной из важнейших сторон деятельности Леонтия (Лебединского) было храмостроительство и восстановление древних православных храмов. В 1877 г. император Александр II утвердил «Правила для устройства церковных зданий в Привислинском крае», руководство строительством осуществляло Министерство внутренних дел. В том же году попечением Леонтия (Лебединского) были открыты два самостоятельных прихода: в посаде Ново-Александрия Люблинской губернии и приграничном местечке Граево Щучинского уезда Ломжинской губернии (22 октября 1878 г. Леонтий (Лебединский) освятил церковь). 14 августа 1879 г. Леонтий издал распоряжение о новом распределении церквей по благочинническим округам и об открытии новых благочиний – всего 19. В епархии начались выборы благочинных, 14 января 1880 г. Леонтий утвердил составленную Холмским духовным правлением инструкцию по их проведению. При Леонтии (преимущественно им лично) были освящены в 1876 г. Крестовоздвиженский собор в Люблине и церковь в Грубешове Холмской губернии, в 1877 г. Петропавловский собор в Калише, Троицкий собор в Варшаве после ремонта, храмы в Ломже, местечке Александрово Нешавского уезда Варшавской губернии (ныне город Александрув-Куявски, Польша), в Янове Люблинской губернии (ныне Янув-Любельски, Польша), в 1878 г. собор в Холме Люблинской губернии, храм в местечке Кодно Житомирского уезда Волынской губернии, церкви при Варшавских мужской и женской гимназиях, в 1879 г. храм Казанской иконы Божьей Матери в Августове Сувалкской губернии, церковь в Млаве Плоцкой губернии, в 1880 г. храмы в Слупцах Калишской губернии, посаде Кибартах Сувалкской губернии (ныне город Кибартай, Литва), в 1881 г. церкви в Годышеве и Граеве, а также после ремонта Успенский собор в Сувалках и в селе Лесна Константиновского уезда Седлецкой губернии (ныне Лесьна-Подляска, Польша), в 1886 г. в Плонске Полоцкой губернии, в 1889 г. колокольня в Лукове Люблинской губернии, в 1890 г. собор Рождества Пресвятой Богородицы в Беле Седлецкой губернии (ныне Бяла-Подляска, Польша), церковь в Коло Калишской губернии, храмы в городах Грубешове Холмской губернии, Беле Седлецкой губернии (ныне Бяла-Подляска, Польша) и др. Леонтий (Лебединский) поддержал инициативу командующего Варшавским военным округом Иосифом Владимировичем Гурко (с 1883 г – генерал-губернатор Привислинского края) по созданию войсковых церквей, на средства военного ведомства были оборудованы несколько гарнизонных храмов, в частности, в Щучине (1890 г.) и Гонсиорове Ломжинской губернии, а также близ города Остроленки (1891 г.). Подавляющее большинство этих церквей на территории Польши были разрушены или капитально перестроены в 1920–1970 гг. В 1877 г. были открыты церковноприходские попечительства в Люблине, Грубешове и Пултуске Ломжинской губернии, в 1878 г. – при церкви в Янове, всего 17 приходских попечительств, или братств. В Седльце были устроены Леонтиевская церковь-школа и при ней Братство Леонтия Ростовского. Леонтий (Лебединский) занимался вопросами правильного использования финансовых средств приходов, созданием эмеритальной кассы для епархиального духовенства (1878 г.). В 1882 г. Яблочинский во имя преподобного Онуфрия Великого монастырь был возведён в первый класс.