La région du parc a été habitée par diverses tribus aborigènes depuis plus de . Elle est également l'une des premières régions en Amérique à être fréquentées par les Européens. En effet, les Vikings la fréquentaient à partir du . Ils furent suivis par les pêcheurs basques, français et anglais. La région fut longtemps disputée entre les Français et les Britanniques. Ces derniers en obtinrent officiellement le contrôle au début du , mais les Français conservèrent tout de même des droits de pêche et de séchage du poisson. La premiers habitant permanents s'établirent à partir du . Ils pratiquaient la pêche et l'exploitation forestière. Le parc fut créé en 1973. En 1987, il fut reconnu par l'UNESCO en tant que site du patrimoine mondial pour son histoire géologique et la beauté de ses paysages.