The museum building in Yekaterinburg is one of the oldest surviving structures in the city. It was built in the 1730s and early 1740s as a hospital for the Yekaterinburg ironworks and has undergone numerous changes in purpose and reconstruction. Initially, the complex consisted of four buildings arranged around an inner courtyard: the hospital was located in the northeast, the mint in the northwest, the pharmacy in the south, and the assay laboratory and fur shop in the southwest, where there was also a factory prison. The building is included in the list of cultural heritage sites of the Sverdlovsk region, as it hosted the first theatrical performance in Yekaterinburg. On November 5, 1843, Kazan entrepreneur P. A. Sokolov presented the opera 'The Moonlight Woman' and the vaudeville 'The Little Foot', marking the beginning of the city's theatrical history and the founding date of the first City Theater. In the 19th century, the building underwent several reconstructions. In 1867, the Alexandrovsk City Almshouse opened here, after which a second floor was added to the western building. In 1895 and 1898, the Nikolayev House Church was built inside the building with funds from merchant D. I. Lagutyaeva, and in 1899, a bell tower was erected above the church, which has not survived to this day.

In the 1970s, during the reconstruction of 'Plotinka', it was decided to preserve the building, while most of the former Yekaterinburg factory was demolished, and a Historical Square was laid out in its place. In the late 1970s, the idea of reconstructing and repurposing the building into a museum emerged. The project was developed by a group of architects led by G. Belyankin and A. Ptashnik. The renovation was completed in 1985, and the museum opened on May 9, 1986. The inner courtyard was covered with a lightweight roof, and the opening facing the embankment was enclosed with a glass wall. The new hall housed a collection of Ural cast iron, with the unique Kaslin cast iron pavilion as its centerpiece.

The second building of the Yekaterinburg Museum of Fine Arts, located at 11 Vainera Street, was built in 1912 according to the design of architect K. T. Babikin for the shop of Yekaterinburg merchant Bardygin. In 1936, the first exhibitions of the Sverdlovsk Picture Gallery were housed here, which received the status of a museum of fine arts in 1988. Collections of Russian artistic avant-garde from the 1910s and 1920s, domestic art from the 1920s to the 1950s, and later periods were exhibited here. Temporary exhibitions were held in the large exhibition hall. After the building's reconstruction in 2020, the opening of the 'Hermitage-Ural' center was planned, first postponed to April 2021, and then to the end of the first half of 2021.

The Sverdlovsk Picture Gallery was founded in 1936 and renamed the Sverdlovsk Museum of Fine Arts in 1988. In 1992, with the return of the city's historical name, it became the Yekaterinburg Museum of Fine Arts. The foundation of the collection was formed by the collection of the Ural Society of Natural Science Lovers (UOLE), which until 1936 was part of the Natural History Local History Museum and was then transferred to the picture gallery.

During the Great Patriotic War, treasures from the State Hermitage, evacuated from Leningrad, were stored in the gallery building. Hermitage staff had a significant impact on the formation of the collection, the scientific activities of the gallery, and the cultural life of the city.

Later, works from the State Hermitage, the Tretyakov Gallery, and the State Pushkin Museum were added to the museum's collection. By the mid-1980s, with the growth of the collection, the need for expansion of storage and exhibition spaces arose. In 1986, part of the exhibition was moved to the reconstructed building of the former hospital of the Yekaterinburg ironworks at 5 Voievodina Street. The Kaslin cast iron pavilion was dismantled, relocated, and restored.

Since 1988, the museum has actively worked on expanding its collection, organizing departments for Russian painting, decorative and applied arts, and domestic art of the 20th century. This was a period of active scientific and publishing activities for the museum, which gained wide recognition and established contacts with scientific and museum centers in Russia and abroad.

In 2008, the Regional Center for Museum Pedagogy and Creative Development for Children and Youth was established at the museum, in collaboration with the Russian Center for Museum Pedagogy and Children's Creativity of the Russian Museum. The center develops the museum's ties with the school education system and implements joint projects and programs.

Since 2011, the museum has held the International Mezzotint Festival, the largest artistic project in the Urals, bringing together artists from more than forty countries working in this complex graphic technique.

In September 2014, the director of the State Hermitage Mikhail Piotrovsky, the governor of the Sverdlovsk region Yevgeny Kuyvashev, and the head of the Yekaterinburg administration Alexander Yakob signed an agreement to create the cultural and educational center 'Hermitage-Ural', with its opening planned for 2020.

In 2015, the head of Yekaterinburg Yevgeny Roizman transferred his collection of naive art to the museum, initiating the creation of a new division, the 'Museum of Naive Art'. The museum opened at 18 Rosa Luxemburg Street in November 2017.