Der Überlieferung nach befindet sich die Burg an der Stelle einer älteren Befestigung, in der sich der Stein von Scone befunden haben soll, bevor dieser im 9. Jahrhundert nach Schloss Scone gebracht wurde.

Die heutige Festung wurde um das Jahr 1220 von Duncan Dubhgall, einem Enkel von König Somerled, oder seinem Sohn Ewen für den MacDougall-Clan errichtet. Dunstaffnage Castle gilt für die Erbauungszeit als eine der mächtigsten Festungen im westlichen Schottland.[1]

1308 oder 1309[2] wurde Dunstaffnage nach der Schlacht von Brander von Robert the Bruce eingenommen und blieb etliche Jahre in königlichem Besitz. Die Festung ging 1469 in den Besitz des Herzogs von Argyll und damit des Clan Campbells über. Von diesem wurde die Burg bis zu den Jakobitenaufständen militärisch genutzt. Flora MacDonald, die Bonnie Prince Charlie nach dessen Niederlage bei Culloden zur Flucht vor den englischen Truppen verhalf, war 1746 kurzfristig in Dunstaffnage inhaftiert, bevor sie weiter nach London gebracht wurde.

Nach einem Brand des Torhauses im Jahre 1810[3] stand die Anlage leer und verfiel. Erst 1904 wurde das Torhaus wieder rekonstruiert.