Οι άνθρωποι ζούσαν στο Σάλτσμπουργκ από τη Νέα Λίθινη Εποχή μέχρι σήμερα. Το παλαιότερο εύρημα στην περιοχή της πόλης χρονολογείται γύρω στο 4500 π.Χ. Από το 15 π.Χ. και μετά, μετά τη ρωμαϊκή κατοχή, η πόλη ονομαζόταν Iuvavum. Η ρωμαϊκή πόλη βρισκόταν στη σημερινή παλιά πόλη γύρω από την πλατεία Waagplatz. Η πόλη έγινε σημαντικός τόπος από τα ανατολικά προς την επαρχία της Γερμανίας. Οι Ρωμαίοι έφυγαν με την έναρξη της βαρβαρικής μετανάστευσης γύρω στο 500. Μέχρι το 696 μόνο λίγα μπορούν να ειπωθούν για την ιστορία της. Το 696 η πόλη δόθηκε στον επίσκοπο Ρούπερτ από τον δούκα Θεόδωρο Β΄ της Βαυαρίας. Ο Δούκας διέταξε τον Ρούπερτ να φέρει τον χριστιανισμό στα ανατολικά και νοτιοανατολικά της χώρας του. Ο Ρούπερτ ίδρυσε το μοναστήρι του Αγίου Πέτρου και για τις γυναίκες το μοναστήρι Nonnberg. Το 739 το Σάλτσμπουργκ έγινε έδρα επισκόπου και το 774 χτίστηκε ο πρώτος καθεδρικός ναός. 998 Το Σάλτσμπουργκ έγινε αρχιεπισκοπή που κυβερνούσε ολόκληρη τη βαυαρική περιοχή.
Κατά τον Μεσαίωνα το Σάλτσμπουργκ έγινε πλούσιο από το εμπόριο αλατιού από το κοντινό Ντύρνμπεργκ στο Χάλεϊν. Μέχρι τον 14ο αιώνα το Σάλτσμπουργκ ήταν ανεξάρτητο από τη Βαυαρία και αποτελούσε κράτος της Αγίας Ρωμαϊκής Αυτοκρατορίας. Οι πολίτες του Σάλτσμπουργκ βρίσκονταν υπό τις διαταγές του αρχιεπισκόπου σε αντίθεση με άλλες πόλεις της αυτοκρατορίας. Στην εποχή του μπαρόκ διαμορφώθηκε η όψη της σημερινής πόλης. Ο καθεδρικός ναός ανοικοδομήθηκε σε στυλ μπαρόκ. Οι περισσότεροι αρχιτέκτονες προέρχονταν από την Ιταλία. Το 1622 ιδρύθηκε πανεπιστήμιο. Λόγω του γεγονότος ότι επρόκειτο για καθολικό κράτος οι Προτεστάντες είχαν σοβαρή θέση στο Σάλτσμπουργκ. Ωστόσο, το 1731 οι Προτεστάντες, οι οποίοι δεν επέστρεφαν στην καθολική πίστη, έπρεπε να εγκαταλείψουν το Σάλτσμπουργκ μέσα σε οκτώ ημέρες.
Στις αρχές του 19ου αιώνα ο Ναπολέων Βοναπάρτης προώθησε το Δουκάτο του Σάλτσμπουργκ, το οποίο αργότερα αποτέλεσε τμήμα του Βασιλείου της Βαυαρίας. Στη συνέχεια, το Σάλτσμπουργκ προσαρτήθηκε από την Αυστρία, επέστρεψε στη Βαυαρία και μοιράστηκε μεταξύ Βαυαρίας και Αυστρίας. Το 1918 το Σάλτσμπουργκ έγινε ομόσπονδο κρατίδιο της νέας Δημοκρατίας της Αυστρίας. Το 1938 η Γερμανία προσάρτησε την Αυστρία και το Σάλτσμπουργκ αποτέλεσε μέρος της Γερμανίας. Το 1945, όταν η Αυστρία ανεξαρτητοποιήθηκε από τη Γερμανία, το Σάλτσμπουργκ έγινε και πάλι ομόσπονδο κρατίδιο.
