right|thumb|Port Royal, gravure de 1609 Période autochtone
Les premières traces de peuplement humain dans l’actuelle Nouvelle-Écosse suivent immédiatement le retrait des glaciers lors de la fin de la dernière période glaciaire, soit il y a 10 000 à 13 000 ans. Il s’agit d’outils de pierre et de vestiges de campements de chasseurs-cueilleurs de la période paléoindienne (13 000 à –9 000 ans avant ce jour).
Étrangement, il existe très peu de traces de peuplement humain dans la période située entre 10 000 et 5 000 ans avant ce jour. On parle de cette époque comme du « grand hiatus ». Plusieurs hypothèses d’ordre surtout écologique ont été avancées pour expliquer cette absence mais aucune n’a pu être démontrée.
Par contre, la période immédiatement postérieure, qui va jusqu’à il y a 2 500 ans révèle de nombreuses traces de peuplement humain. Les outils de pierre réapparaissent alors et on trouve parmi eux de nombreux agrès de pêche, indiquant une prépondérance croissante des ressources maritimes dans l’alimentation. Se développe alors la culture dite « archaïque maritime », présente depuis beaucoup plus longtemps au Labrador, à Terre-Neuve et sur la côte du Maine. Outre un important outillage pour la pêche et la chasse aux mammifères marins (poids, harpons, hameçons) une grande variété d’outils conçus pour le travail du bois se trouve dans les sites de cette civilisation. Les rites funéraires élaborés ont laissé des tombeaux dans lesquels les défunts étaient enterrés, recouverts d’ocre rouge et accompagnés d’outils, d’amulettes et de sculpture en pierre représentant souvent des animaux marins. La disparition de cette culture pourrait être reliée à une hausse du niveau de la mer, survenue il y a 3 500 ans, qui submergea l’actuel plateau continental, jusqu’alors émergé. Les sites les plus intéressants se trouveraient alors sous l’eau.
Vers 3 000 ans avant aujourd’hui, la région fut occupée par des peuples de la tradition dite « Susquehanna » venus du sud. Leur mode de vie associait chasse, pêche et cueillette. Vers 2 500 ans, et jusqu’à l’époque du contact avec les Européens (), c’est la période « céramique », correspondant à l’arrivée des peuples Micmacs et Malécites, et se distinguant, comme son nom l’indique, par l’apparition de la poterie, innovation venue du sud comme, sans doute, les Mi'kmacs eux-mêmes si on en croit leurs traditions orales. La langue micmaque appartient à la famille algonquienne, comme le malécite, l’abénaki, le cri, l’innu et la plupart des langues parlées dans le nord-est de l’Amérique.
Au , les Micmacs entrent dans une phase d’expansion et leur territoire couvrira, à l’arrivée des Européens, environ dans les trois Provinces maritimes et la Gaspésie. Ce sont eux que les Français appelleront les « Gaspésiens ». Ce territoire sera divisé en 7 districts. Ces districts reconnaissent chacun un « sagamo » ou chef dont la principale fonction est l’attribution des territoires de chasse et de pêche. Il n’a guère d’autres pouvoirs et, pour le reste l’organisation politique micmaque est semblable à celle des autres peuples algonquiens de l’est canadien : on vit en villages restreints comprenant quelques familles et le rôle de chef est reconnu, de façon temporaire et informelle, aux individus faisant preuve de compétences reconnues par tous. L’institution du « sagamo », toutefois, est particulière aux Micmacs et pourrait indiquer une influence méridionale, de même que la place importante tenue par le culte du soleil dans leur religion. Par ailleurs, celle-ci comporte un recours au shaman, comme chez les autres peuples algonquiens. Les bandes se regroupent en été pour la pêche et se divisent en hiver pour chasser à l’intérieur des terres. La cueillette et, par endroits, une agriculture d’appoint, permettent de combler les besoins. L’habitation est composée de cabanes en perches recouvertes d’écorces, certains villages côtiers sont entourés de palissades.
La population totale est difficile à évaluer. Les estimés les plus fréquents parlent de 5 à 6 000 personnes mais, selon certains auteurs, il y a pu y avoir jusqu’à 35 000 Micmacs juste avant le contact avec les Européens. Il est sûr que les guerres et les épidémies des trois siècles qui suivirent réduisirent considérablement la population autochtone, ici comme ailleurs en Amérique.
Premières explorations
Il est difficile de dire avec certitude qui fut le premier Européen à toucher les côtes de la Nouvelle-Écosse. Outre les spéculations autour de la venue de Scandinaves médiévaux, alimentées par la découverte d’une monnaie norvégienne du dans l’État du Maine, il n’est pas du tout certain que Giovanni Cabotto (John Cabot) ait touché terre à l’endroit qui s’appelle aujourd’hui Cabot’s trail, lors de son voyage de 1497. Il a, en tout cas, longé la côte et, ayant identifié les Grands Bancs de morue de Terre-Neuve, il a suscité l’invasion de pêcheurs européens dans le Golfe du Saint-Laurent qui se produisit au .
En 1524, Giovanni Verrazano, au service du roi de France, cartographia la côte atlantique de l’Amérique du Nord et lui donna le nom « Arcadie », inspiré de la mythologie antique (nous sommes à la Renaissance). Ce terme donna naissance au nom « Acadie ». Il est possible que le nom se soit confondu avec le terme d’origine micmaque « cadie » qui désignerait un port. Le Florentin fut suivi de près par le portugais Gomes, au service de l’Espagne.
La présence accrue des pêcheurs et baleiniers européens dans les eaux du nord-est américain eut pour conséquence le développement du commerce des fourrures avec les Autochtones et, subséquemment, le développement de compagnies à monopole. Il s’ensuivit une volonté, de la part des puissances européennes, de s’assurer le contrôle des voies stratégiques permettant l’accès à ce commerce. La France désirant s’assurer le contrôle de l’embouchure du Saint-Laurent, l’aube du vit l’envoi de plusieurs expéditions chargées de trouver un emplacement favorable à l’établissement d’une colonie. La première tentative, à l’île de Sable en 1598, se termina en désastre et quelques survivants faméliques durent être rapatriés.
Colonisation européenne
En 1604, Pierre du Gua de Monts, marchand huguenot, fut chargé par Henri IV de la colonisation de ce qu’on appelait de plus en plus souvent l’Acadie. Associé au noble Jean de Poutrincourt et au géographe Samuel de Champlain, il procéda, cette année-là à la fondation de Port Royal, aujourd’hui Annapolis Royal. Les contacts avec les Micmacs furent suffisamment bons pour que la colonie, abandonnée en 1607 par manque de vivres, soit laissée sous la garde du sagamo Membertou.
Les Français étaient de retour en force en 1610. Les rivalités coloniales troublèrent rapidement la paix : dès 1613, une attaque virginienne ravagea la colonie et, en 1621, le roi Jacques VI d’Écosse accorda à sir William Alexander, une charte l’autorisant à établir une colonie écossaise en Acadie et le nom « Nova Scotia » (Nouvelle-Écosse) apparut sur les cartes.
En 1628, les frères Kirke, corsaires britanniques, prirent la colonie et des colons Écossais débarquèrent. Trois ans plus tard, la colonie fut rendue à la France par traité et les Écossais furent expulsés pendant que 300 colons français, sous la direction du sieur Isaac de Razilly, venaient s’installer. La colonie relevait désormais de la Compagnie des Cents Associés, qui devait procéder à la colonisation, en échange du monopole de la traite des fourrures.
Cela mettait la colonie sous la dépendance du gouverneur de la Nouvelle-France installé à Québec. Cependant, celui-ci était bien loin et l’Acadie fut, de fait, laissée à un abandon presque total. Aussi, lorsque Razilly mourut, la même année, et que son domaine fut partagé entre les sieurs Charles de Menou d'Aulnay et Charles La Tour, les deux seigneurs entrèrent en une rivalité qui dégénéra vite en une véritable guerre privée qui culmina avec le massacre de la garnison du fort La Tour, par d’Aulnay, en 1645. La Tour intriguant avec les Anglais, une force anglaise prit la colonie en 1654. Rendue à la France en 1667, la colonie fut de nouveau l’objet d’attaques anglaises en 1690, et puis d'attaques britanniques en 1707 et en 1710.
Les Traités d'Utrecht (1713) cédèrent l’actuelle Nouvelle-Écosse, à l’exception de l’île Royale (aujourd’hui île du Cap Breton) à la Grande-Bretagne. Les régions qui constituent aujourd’hui le Nouveau-Brunswick et l’île-du-Prince-Édouard restèrent à la France. Cependant, la majorité des 4 000 habitants désignés désormais comme Acadiens se retrouva sous domination britannique. Malgré toutes ces péripéties, la colonie avait relativement prospéré. Les Acadiens, contrairement à la plupart des colons européens en Amérique, avaient développé de nouvelles terres, non en défrichant la forêt, mais en gagnant sur la mer, grâce à un réseau de digues, les aboiteaux, et de canaux inspirés de la technique des marais poitevins, région dont plusieurs étaient originaires. Le développement de l’agriculture ainsi qu’un commerce important avec les colonies voisines, y compris britanniques malgré les guerres et les interdictions, permit à la population d’augmenter rapidement (ils seront 15 000 en 1755). Cette évolution était d’autant plus nécessaire que les pandémies successives qui frappèrent la population autochtone avaient réduits le nombre de Micmacs et Malécites au point que ceux-ci n’étaient plus en mesure de ravitailler la colonie. D’ailleurs le troupeau d’orignaux de l’île Royale fut exterminé au milieu du et la population micmaque de l’île émigra.
La « Nouvelle-Écosse » et l’Acadie française thumb|300px|Vue du débarquement des troupes de Nouvelle-Angleterre sur l'île de Cap Breton pour attaquer Louisbourg en 1745. (Dessin de 1747) thumb|300px|Le siège de Louisbourg en 1745. (Gravure allemande anonyme du ) La période qui va de 1714 à 1755 fut celle d’un face-à-face stratégique entre grandes puissances. D’un côté, la France, désireuse de combler le vide laissé par l’abandon de sa portion de l’Acadie, investit dans le développement d’une nouvelle « Acadie française », dont le centre fut la ville-forteresse de Louisbourg, située sur l’île Royale, dont la construction commença en 1718. Les coûts de la construction furent exorbitants et les délais nombreux mais, en quelques décennies, Louisbourg devint, avec 4 000 habitants, la plus grande agglomération de l’empire français d’Amérique du Nord et un haut lieu du commerce transatlantique… ainsi que de la contrebande avec les colonies britanniques. Ceci bien que peu d’Acadiens ait quitté leurs terres pour s’établir dans cette île rocailleuse. Parallèlement, un début de colonisation française se fit aux îles de la Madeleine, à l’île Miscou et à l’île St-Jean, données d’abord en fief au comte de Saint-Pierre, puis royalisées en 1724.
Du côté britannique, la colonie de Nouvelle-Écosse connut un développement important à travers l’augmentation de la population et le développement du commerce avec les colonies britanniques et françaises malgré l’interdiction de ce dernier par le Parlement britannique en 1722. Le principal problème tenait au statut incertain de la population acadienne, qui refusait en masse de prêter le serment d’allégeance à la couronne exigé par le gouvernement colonial. Cette situation incitait Londres à refuser à la colonie les institutions coutumières aux colonies britanniques (chambre d’assemblée, habeas corpus, etc.) et à maintenir un régime militaire. Les colons britanniques, par conséquent, tendaient à bouder la Nouvelle-Écosse qui demeurait une enclave française dans l’empire britannique.