Будівництво палацу Потоцьких розпочалось у 1880 році, після того як родина Потоцьких продавши свій палац на площі Галицькій, придбала у 1822 році нерухомість по вул. Широкій. Старий палац (невеличка садиба) був розібраний у 1860-1861 роках, однак спорудження нової резиденції затягнулось на три десятиріччя.
Палац Потоцьких було збудовано за проектом французького архітектора Людвіга де Верні та англійського архітектора Юліана Цибульского у стилі барокового класицизму на місті старого палацу Потоцьких.
До 1879 року на місці палацу знаходився великий міський парк, в якому після 1980-х років побудували шахту для прокладання тунелів підземного трамваю. В цей же час до палацу Потоцьких приєднали непривабливу прибудову, в якій в наш час знаходиться Музей мистецтва давньої український книги.
План палацу Н-подібний, триповерховий. Фасади палацу прикрашені фігурними обрамленнями вікон, ліпними консолями балконів та балюстрадами. Парадний вхід оформлений арочним портиком з ліпниною та іонічними колонами. Загальна площа палацу становить 3100 кв.м.
З 1972 року до 2000-х років у палаці Потоцьких розмістився Палац урочистих подій (Львівський міський РАГС). На початку нашого століття палац Потоцьких був переданий Львівській галереї мистецтв.