Like the rest of the areas around Lake Mälaren, Salem has a significant amount of ancient remains, as far back as the Stone Age. The church of Salem traces its foundation to the 12th century.
Just like its eastern municipal neighbour Botkyrka, Salem traces its history back to the legendary Saint Botvid, who lived in the area sometime between 1050-1120. In the medieval tradition, a spring would always be found in connection to the death of a saint. According to legend, when the remains of Saint Botvid were transported to the church in today's Botkyrka, the casket was temporarily put down near the shore of Lake Bornsjön, where a spring poured up. It continues to provide clear water to this day.
Salem was united with the municipality of Botkyrka during the Swedish municipal reform between 1971-1974. However, in 1983, after energetic protests, they were split apart, and Salem became the 14th smallest municipality by area in the country.