Kanada történelme sok ezer évvel ezelőtt kezdődött, mikor az indiánok ősei a Bering-szoroson keresztül megérkeztek Észak-Amerikába. Az őslakos népek kialakították saját kultúráikat, kereskedelmi hálózataikat és társadalmi rendszereiket. Európaiak először a 10. században érkeztek Kanadába, de a vikingek megtelepedési próbálkozása sikertelennek bizonyult. A 15. század végétől kezdődően francia és brit telepesek kezdték el gyarmatosítani Észak-Amerika atlanti partvidékét. A hétéves háborúban Franciaország szinte valamennyi északkelet-amerikai területét átengedte Nagy-Britanniának. 1867-ben az észak-amerikai brit gyarmatokat a Kanadai Konföderációban egyesítették, amely domíniumi státuszt kapott. Az 1931-es westminsteri statútum révén Kanada teljes függetlenséget kapott, olyan királysággá alakult, melynek a mindenkori brit uralkodó az államfője. 270px|bélyegkép
Őslakos kultúrák Az utolsó eljegesedés idején (Észak-Amerikában Wisconsin-, Európában Würm-eljegesedés), 50-17 ezer évvel ezelőtt a szárazföldekre telepedő jégrétegek miatt az óceánok szintje lesüllyedt és a szibériai népcsoportok a mai Bering-szoros helyén húzódó földhídon átkelhettek Alaszkába. Továbbhaladásukat ekkor megakadályozta az észak-amerikai jégpajzs, ám mintegy 16 ezer évvel ezelőtt egy melegebb időszakban a gleccserek elolvadtak és az első emberek a mai Kanada területére léphettek. Ennek időpontja és a vándorlások útvonala vitatott. Az emberi tevékenység legkorábbi nyomai a Haida Gwaii-szigeteken, Old Crow Flats-en és a Bluefish-barlangban kerültek elő.
Egy újabb lehűlést követően az észak-amerikai klíma i.e. 8000 után stabilizálódott. A jégpajzs csak lassan olvadt el és nyomában hatalmas olvadékvíz-tavak maradtak. A lakosok továbbra is vándorló vadász-gyűjtögetők voltak, de idővel így is kialakultak az egyes tájegységekre jellemző kultúrák (paleoarktikus, Plano- és tengeri csoportok).
A Woodland kultúrperiódus kb i. e. 2000-től i. sz. 1000-ig tartott és az ontariói, quebeci és tengeri régiókra terjedt ki. A Woodland-kultúrákat elsősorban az agyagedények használata különbözteti meg a korábbi népcsoportoktól; a legrégebbi kanadai cserépedények Ontario területén kerültek elő.
I. e. 300 és i. sz. 500 között a Mississippi és az Appalache-hegység közötti folyóvölgyekben a Hopewell-kultúrák virágoztak, melyek kereskedelmi hálózata kiterjedt az Ontario-tó északi partjaira is. A Hopewell csoporthoz Kanadában a Point-félszigeti, Saugeen- és Laurel-kultúrák tartoztak. bélyegkép|bal|Észak-amerikai Hopewell-kultúrák A leendő Kanada keleti erdőségeit algonkin és irokéz törzsek lakták. Az algonkin nyelv feltehetően a mai Idaho nyugati síkságairól származik, beszélői onnan indultak kelet felé, míg el nem érték a Hudson-öblöt és Új-Skóciát, délen pedig Virginiát. Kanadában a kelet-algonkin nyelveket beszélő mikmak és abenaki indiánok éltek és feltehetően szintén ehhez a csoporthoz tartozott a kihalt új-fundlandi beothuk is. Az ozsibvék hagyományai szerint a tenger mellől vándoroltak a későbbi Nagy-tavak környéki földjükre, 796-ban az otavákkal és a potavatomikkal megalapították a Három Tűz Tanácsát.
A mai New York állam északi része i. sz. 1000 körül már az irokézek földjének számított, de befolyásuk kiterjedt a mai Ontario tartomány déli részére és Montreal környékére. Hagyományuk szerint 1142-ben alapították meg az Irokéz Konföderációt. A Kanadába is átnyúló észak-amerikai Nagy Síkságon a szintén egy közép-algonkin nyelvet beszélő törzs, a krík voltak az urak, akik elsősorban bölényvadászatból éltek. Északnyugaton a na-dené nyelveket beszélő törzsek éltek, többek között az atapaszkák és a dél-alaszkai szigeteken és Brit Columbia északi részén lakó tlingitek. A na-dené nyelvcsalád feltehetően rokonságban áll a szibériai jenyiszeji nyelvcsaláddal, vagyis észak-amerikai jelenléte egy különálló migrációs hullám következménye lehet.
Brit-Kolumbia belső területeinek lakói a szalis családba tartozó nyelveket (szusvap, okanagan) beszélték, illetve az olyan dél-atapaszka nyelveket, mint a dakelh vagy csilkotin. Brit-Kolumbia partvidékén az öblökben és völgyekben sajátos kultúra alakult ki, amelynek jellemzői a vörös cédrusból épített házak, bálnavadászat és a művészien faragott totemoszlopok voltak.
Kanada északi, sarkvidéki szigetvilágában kezdetben a pre-inuit dorseti kultúra terjedt el, melynek legkorábbi nyomait i. e. 500 körülre datálják. Őket i. sz. 1500 körül az inuitok váltották fel. A régészeti leleteket az inuit szóbeli hagyomány is megerősíti, mely szerint elűzték az "első lakosokat", a tuniitokat.
Az első európaiak bélyegkép|Viking telep L’Anse aux Meadows-nál Európai felfedezők az izlandi viking sagák tanúsága szerint a 10. század végén érkeztek először Kanada partjaihoz. A sagák leírják, hogy az első aki meglátta az új kontinenst, Bjarni Herjólfsson volt, aki 985-ben (vagy 986-ban) Izlandról Grönlandra tartott, de egy vihar délre sodorta. Ő nem kötött ki, de Leif Eriksson 1001 körül expedíciót indított az ismeretlen föld felderítésére és három helyen is kikötött, Hellulandon (feltehetően a Baffin-sziget) Marklandon (talán Labrador) és Vinlandon (talán Új-Fundland). A vikingek megpróbáltak letelepedni az új földön, de harcokba keveredtek az őslakosokkal és kénytelenek voltak visszatérni grönlandi kolóniájukba. Településük maradványait megtalálták az új-fundlandi L’Anse aux Meadows-nál, a szénizotópos kormeghatározás szerint a faházakat 990-1050 körül építették.
A következő európai felfedezők csak ötszáz évvel később, 1497-ben érkeztek, amikor az olasz származású, az angol korona szolgálatában álló John Cabot újra felfedezte Új-Fundlandot. A tordesillasi szerződés alapján Portugália magáénak követelte a Cabot által felderített szigetet és 1499-ben ideküldték João Fernandes Lavradort, aki felfedezte a róla elnevezett Labrador-félszigetet. 1501-1502-ben a Corte-Real fivérek feltérképezték Új-Fundland és Labrador partvidékét és a földet a portugál korona birtokának nyilvánították. 1506-ban I. Manuel király már adót vetett ki az Új-Fundlandnál kifogott tőkehalakra. João Álvares Fagundes és Pêro de Barcelos 1521 körül több halásztelepet is alapított a kanadai partok mentén, de ezeket később elhagyták a jövedelmezőbb dél-amerikai gyarmatok kedvééért.
Angol és francia gyarmatosítás bélyegkép|bal|Quebec 1608-ban I. Ferenc francia király 1524-ben megbízta Giovanni da Verrazzanot, hogy Florida és Új-Fundland között próbáljon átjárót keresni a Csendes-óceánra. 1534-ben Jacques Cartier Gaspésie félszigetén felállított egy keresztet és a földet francia tulajdonnak nyilvánította. A franciák több kolóniát is alapítottak a 16. században (Cartier Charlesbourg-Royalt 1541-ben, de La Roche-Mesgouez márki Sable Island-en 1598-ban vagy François Gravé Du Pont Tadoussac-ot 1600-ban), de ezek a próbálkozások elhaltak. Bár állandó településeket nem sikerült alapítani, a francia hajók rendszeresen halásztak Kanada atlanti partvidékén és a Szent Lőrinc-folyónál és az indiánokkal is kereskedtek.
1604-ben Pierre Dugua Sieur de Monts királyi monopóliumot szerzett az észak-amerikai prémkereskedelemre. Dugua egy kereskedőtelepet hozott létre a Saint Croix-folyó torkolatában fekvő szigeten. Egyik beosztottja, Samuel de Champlain feltérképezte a mai Egyesült Államok északkeleti partvidékét, majd 1605-ben átköltöztette a telepet Port Royal-ba (ma Annapolis Royal, Nova Scotia).
Champlain 1608-ban megalapította Quebecet, amely az első állandó francia településsé, és Új-Franciaország fővárosává nőtte ki magát. Quebecet bázisként használva Champlain több expedíciót indított a belső területek felderítésére. 1609-ben ő fedezte fel a Champlain-tavat. 1615-ben kenuval felhajózott az Ottawa-folyón a huronok területének központjába, akikkel szövetséget kötött és segítette őket az irokéz közösséggel szembeni harcukban. Ennek eredményeképpen az irokézek ellenségessé váltak a franciákkal szemben és akadályozták a prémkereskedelmet (ezek az ún. „hódháborúk”), egészen az 1701-es montreali békekötésig.
Az angol Humphrey Gilbert 1583-ban brit birtokká nyilvánította az új-fundlandi, akkor még állandó lakosokkal nem rendelkező Saint John's-t. I. Jakab idejében még alapítottak néhány kisebb kolóniát a szigeten (Cupids, Ferryland), de a délebbi, virginiai gyarmatok jóval sikeresebbnek bizonyultak. 1622-ben skót telepesek érkeztek Nova Scotia-ba, de kezdeti próbálkozásaik nem jártak sikerrel míg 1629-ben a harmincéves háborún belüli ellenségeskedéseknek vége lett Anglia és Franciaország között. Telepeiket azonban fel kellett számolniuk, miután a Saint-Germain-en-Laye-i békében az angolok lemondtak Nova Scotia-ról a franciák javára. Az ezután következő francia betelepülési hullám eredménye volt Kanada második állandó városának, Trois-Rivières-nek megalapítása 1634-ben.
Erre a korszakra jellemző, hogy a délebbi angol gyarmatokon nagyobb volt ugyan a népsűrűség, de a mezőgazdasággal foglalkozó gyarmatosok elsősorban a tengerpart környékére koncentrálódtak. A franciák ezzel szemben jóval mobilabbak voltak, hatalmas területeket vontak ellenőrzésük alá, ahol elsősorban prémkereskedelemből származott a jövedelmük, hittérítők látogatták az indiánokat és a fontos útvonalak védelmére a szárazföld belsejében is épültek erődök.
Champlain 1635-ös halála után megerősödtek a katolikus egyház és a jezsuiták erőfeszítései az indiánok megtérítésére és egy olyan intézményrendszer kialakítására, ahol az őslakosok és európaiak békében élhetnek egymással. 1642-ben a szulpiciánusok rendje pénzzel támogatta Paul Chomedey de Maisonneuve-t és telepeseit, akik megalapították a mai Montreal elődjét, Ville-Marie-t. 1663-ban a francia korona az Új-Franciaország Társaság révén közvetlen irányítása alá vonta az északkelet-amerikai gyarmatokat. A bevándorlás viszonylag alacsony maradt, de ezt részben kompenzálta a nagyobb termékenység; a statisztikák szerint a kolóniákon élő francia nőknek 30%-kal több gyermeke született, mint az anyaországbelieknek. Az 1666-os népszámlálás során 3215 franciát számoltak össze Acadiában, melynek azonban kétharmada férfi volt.
Gyarmati háborúk bélyegkép|Észak-amerikai gyarmatok 1702-ben Az 1700-as évek elejére Új-Franciaország európai származású lakossága a Szent Lőrinc-folyó partjain és Nova Scotiában elérte a 16 ezret. A következő évtizedekben azonban a bevándorlás nagyon lelassult, így az 1750-es évekre az északkelet-amerikai angol telepesek létszáma már tízszeresen meghaladta a franciákét. 1670-től a Hudson-öböl Társaság révén az angolok északon, Rupert's Land-en is megtelepedtek és Új-Fundlandon is fenntartották halásztelepeiket. A francia prémkereskedők ellenségesen fogadták a konkurens Társaság megjelenését és Pierre Troyes 1686-ban Montrealból kiindulva expedíciót vezetett a Hudson-öbölhöz és több brit állomást megszállt. Miután La Salle felfedezte a Mississippi völgyét, azt is francia birtoknak nyilvánította és a franciák itt is létrehozták elszórt kereskedőállomásaikat és erődjeiket.
1689 és 1763 között négy francia-indián háború, Új-Franciaország és a brit Tizenhárom gyarmat között pedig két háború zajlott. 1689-1697-ben Vilmos király háborúja idején több csatára is sor került az ellenséges országok gyarmati erői között. A ryswicki szerződés után rövid ideig béke honolt, de már 1702-ben kitört Anna királynő háborúja (1702-1713) melyben az angolok elcsatolták Nova Scotiát. A további expanziót megakadályozandó, a franciák felépítették Cape Breton Island-en Louisbourg erődjét, mely a Szent Lőrinc-folyó bejáratát volt hivatott védeni. Az erődöt az 1744-48-as György király háborújában a William Pepperrell vezette angol gyarmati erők három hónapos ostrom után bevették, bár a békekötés után visszakerült francia kézre.