El Museo de Bellas Artes de Salto fue creado el 30 de agosto del año 1945 por iniciativa del Intendente Orestes Lanza.
Su primera sede en calle Uruguay integró sus salas con obras de artistas locales y del Salón Nacional de Bellas Artes. El Museo se traslada en el año 1948 a un edificio de la calle Dr. José Amorín donde permaneció durante casi dos décadas en las que el acervo artístico y la actividad cultural se vio incrementada año a año.
En el año 1963 la familia integrada por los esposos Luis J. Armstrong y María Irene Olarreaga Gallino donan al municipio la residencia de calle Uruguay nº 1067 en tiempos del Intendente Armando I. Barbieri.
Esta suntuosa casa es conocida como el Palacio Gallino por la elegancia de sus ambientes y la fina decoración interior. Dada la incorporación a la colección de objetos de arte aplicado, la mayoría de ellos donados por familias de la ciudad, el museo se llamará en su nueva sede "Museo de Bellas Artes y Artes Decorativas de Salto".
La colección se incrementa constantemente de obras de gran valor artístico, muchas de ellas premiadas en salones nacionales.
A partir de la década del 70 comienzan a realizarse en Salto los Salones de Arte de Primavera, que luego se transformarán en las actuales Bienales de Primavera de Salto, concurso al que acuden los mejores artistas de todo el Uruguay.
En cada edición de las Bienales algunas obras premiadas, incluido el primer gran premio, se integran al acervo del Museo. Esto posibilita la actualización constante de la colección museística, mostrando la evolución de las corrientes y modalidades artísticas nacionales a lo largo de los años.
En el año 1999 es declarado Monumento Histórico Nacional.