thumb|right|Kanadan provinssit ja territoriot vuosina 1867–2000 Kanadan historia alkoi vuosituhansia sitten, kun ensimmäiset ihmiset saapuivat nykyisen Kanadan alueelle Beringinsalmen kautta noin 16 000 vuotta sitten. Paleointiaanit levittäytyivät seuraavien vuosituhansien aikana Kanadaan, kun mannerjäätikkö vetäytyi pohjoiseen. Paleoeskimoiden Dorsetin kulttuuri kehittyi noin 2 500 vuotta sitten, mutta sen syrjäytti noin vuonna 1000 inuittien Thulen kulttuuri. Intiaanit olivat asuttaneet Kanadan, kun ensimmäiset eurooppalaiset saapuivat alueelle. Viikingit asuttivat itärannikkoa hetkellisesti vuoden 1000 paikkeille, ja Kanadan varsinaisesti löysi 1497 Englannin lipun alla purjehtinut John Cabot.
Jacques Cartier saapui 1534 Saint Lawrencen lahdelle ja julisti maat Ranskalle, joka alkoi pian asuttaa Kanadaa. Englanti alkoi kiinnittää enemmän huomiota alueeseen, kun se sai vihjeitä hyvistä turkismaista. Turkiskauppaa siihen asti hallinnut Ranska joutui jatkossa kilpailemaan englantilaisten perustaman Hudson’s Bay Companyn kanssa. Ranska alkoi hiljalleen menettää asemiaan Kanadassa ja seitsenvuotisen sodan päättäneessä Pariisin rauhassa 1763 se menetti Kanadan Britannialle.
Britit jakoivat vuonna 1791 Kanadan kahteen siirtokuntaan, Ylä- ja Ala-Kanadaan, ja vuoden 1812 sodan jälkeen sovittiin Kanadan ja Yhdysvaltain rajasta. Valta oli Kanadassa pienellä brittieliitillä, mikä aiheutti vuonna 1837 kapinan kummassakin siirtokunnassa, ja kolme vuotta myöhemmin muodostettiin Kanadan provinssi, jolla oli oma parlamentti. Kanadan dominio muodostui 1867, ja liittovaltio sai ensimmäisen perustuslakinsa. Kanada suuntautui länteen, ja pian se osti Rupertinmaan, jonka liittämistä viivästytti Louis Rielin johtama Redjoen kapina. Ensimmäisessä maailmansodassa kanadalaiset taistelivat emämaa Britannian rinnalla, mutta sodan jälkeen William Lyon Mackenzie King alkoi vaatia itsenäisyyttä. Westminsterin säädöksen nojalla Kanada itsenäistyi Britanniasta vuonna 1931.
Kanada osallistui toiseen maailmansotaan itsenäisenä valtiona, ja sodan jälkeen se osallistui aktiivisesti kansainvälisten järjestöjen muodostamiseen. Kanada oli muun muassa YK:n ja Naton perustajajäsen. Kanada ajoi Nobelin rauhanpalkinnon saaneen Lester B. Pearsonin johdolla YK:n rauhanturvajoukkoja, joihin se on sittemmin osallistunut aktiivisesti. Ranskankielisen Quebecin ja muun Kanadan välinen suhde alkoi kärjistyä 1960-luvulla, ja Quebec on pyrkinyt eroamaan Kanadasta kansanäänestyksellä vuosina 1980 ja 1995. Lopullisesti Kanada irtautui Britanniasta vasta 1982, kun Britannialta vietiin viimeiset valtaoikeudet. Yhdysvallat, Kanada ja Meksiko sopivat vuonna 1992 NAFTA-vapaakauppa-alueen perustamisesta, ja vuonna 2006 Stephen Harperin hallinto antoi Quebecille kansakunnan aseman.
Alkuperäiskansojen esihistoria thumb|Thulen kulttuuriin liittyvä arkeologinen kohde. Ensimmäiset amerikkalaiset saapuivat Aasiasta Beringinsalmen ylittänyttä Beringian maakannasta pitkin 20 000–40 000 vuotta sitten. New Mexicon Clovisista löydettyjen nuolenkärkien perusteella maakannas ylitettiin noin 16 000 vuotta sitten. Clovisin nuolenkärjet ovat vanhin varmistettu todiste ihmisistä Pohjois-Amerikasta, mutta vanhempiakin, epävarmempia löytöjä on tehty ympäri Pohjois-Amerikkaa. Yukonista Old Crow Flatsin eläinten luut ovat yli 80 000 vuotta vanhoja, mutta tutkijat eivät ole varmoja, ovatko luut ihmisten käsittelemiä.Henriksson, s. 48–49.
Ensimmäiset kanadalaiset olivat suurriistan metsästäjiä. Paleointiaanit alkoivat levittäytyä Amerikkaan, ja mannerjäätikön vetäytyäessä he alkoivat asuttaa yhä pohjoisempia seutuja. Vaikka Wisconsin-jääkauden aikana lähes koko Kanada oli mannerjäätikön alla, niin Kalliovuorten itäpuolella oli jäätön käytävä. Noin 10 000 vuotta sitten paleointiaanit olivat asuttaneet nykyisen Kanadan eteläosat, ja noin 7 000 vuotta sitten mannerjäätikkö oli sulanut. Noin vuonna 4000 eaa. Kanadan pohjoisimpiin osiin muutti metsäasumiseen tottuneita ihmisiä Yhdysvaltain itäosista. Lämpimämpi ajanjakso mahdollisti metsien kasvamisen pohjoisessa, mutta noin vuonna 2000 eaa. alue muuttui uudestaan tundraksi, ja arktiset kulttuurit valtasivat pohjoisosat. Noin vuonna 500 eaa. paleoeskimoiden kulttuurista kehittyi Dorsetin kulttuuri, jonka syrjäytti vuodesta 1000 alkaen Alaskasta tullut inuittien Thulen kulttuuri.
Kanadan alkuperäisasukkaiden historiasta ennen eurooppalaisten saapumista tiedetään hyvin vähän.Henriksson, s. 54. Intiaanit olivat jakautuneet 12 kieliryhmään, ja ne voitiin jakaa edelleen poliittisesti ja kulttuurisesti. Itäisen metsäalueen intiaaniheimot kehittivät metsästykselle, maataloudelle ja kaupankäynnille perustuneen yhteiskunnan, ja he perustivat puolipysyviä kyliä. Erityisesti huronien ja irokeesien parissa muodostettiin poliittisia ja uskonnollisia liittoumia. Sekä Kanadan itä- ja länsirannikon intiaanit perustivat monia poliitisia, yhteiskunnallisia ja kulttuurisia instituutia, kun taas pohjoisosien intiaaneilla ei ollut merkittiviä poliittisia yhteisöjä.
Eurooppalaisten saapuminen pienoiskuva|L'Anse aux Meadowsissa on todisteita viikinkien asutuksesta Varhaisimmat kontaktit Viikingit asuttivat Grönlantia 900-luvun lopulla ja tekivät sieltä matkoja länteen Hellulandiin, Marklandiin ja Vinlandiin. Helluland yhdistetään nykyään Baffininsaareen ja Markland Labradorin rannikkoon, mutta Vinlandin sijainnista ei olla vielä varmoja. Vinland saattoi kuitenkin olla Newfoundlandin pohjoisosasta löytynyt L’Anse aux Meadows, jossa on jälkiä viikinkiasutuksesta.Henriksson, s. 57. Norjalaiset asuttivat Kanadan rannikkoa noin vuonna tuhat mutta lähtivät sieltä todennäköisesti vihamielesten alkuperäisasukkaiden jatkuvien hyökkäysten takia.Zimmerman, s. 828.
Viikinkien jälkeen Kanada sai käytännössä olla rauhassa eurooppalaisvierailijoilta yli 400 vuotta. Muutamia kävijöitä on kuitenkin väitetty olleen, mutta varmoja todisteita on hyvin vähän. Todennäköisesti ainakin lukuisat eurooppalaiskalastajat vierailivat Newfoundlandin matalikoilla jo 1400-luvulla, mutta eivät kertoneet matkoistaan, koska pelkäsivät menettävänsä hyvät kalavedet.Henriksson, s. 58.
Espanjan kruunun alaisuudessa seilannut Kristoffer Kolumbus löysi 1492 Amerikan uudelleen etsiessään meritietä Aasiaan. Pian muutkin monarkit alkoivat lähettää retkikuntia. Venetsialainen Giovanni Cabotto eli englantilaisittain John Cabot saapui 1497 Kanadan rannikolle bristolilaista kauppiaiden ja kalastajien sekä todennäköisesti myös Englannin kuninkaan rahoittamana.Henriksson, s. 59. Hän teki kaksi matkaa ja tutki Labradorin, Newfoundlandin ja ehkä myös Nova Scotian rannikoita. Cabot löysi rannikon kalaisat vedet, ja pian portugalilaiset, ranskalaiset ja espanjalaiset kalastajat saapuivat alueelle. Heitä seurasivat baskivalaanpyytäjät, joista monet pitivät päämaajaansa Labradorin Red Bayssä, josta tuli 1500-luvun suurin valassatama.
Asuttaminen thumb|left|upright|Jacques Cartier’ta pidetään Kanadan löytäjänä. Ranskalainen tutkimusmatkailija Jacques Cartier saapui 1534 Saint Lawrencen lahdelle ja julisti maat kuuluvaksi Ranskalle. Tarinan mukaan kaksi hänen mukanaan ollutta irokeesia olisivat käyttäneet oman kielensä sanaa kanata (”kylä”) Stadaconan irokeesiasutuksesta, minkä Cartier olisi ymmärtänyt väärin paikannimeksi. Toisen teorian mukaan nimi olisi tullut espanjankielisestä ilmauksesta cà nada (”ei mitään täällä”).
Cartier purjehti vuonna 1535 Saint Lawrence -jokea pitkin pidemmälle. Hänen löytönsä innoittivat Ranskan kuningas Frans I:stä haastamaan Espanjan uuden maailman herruudesta ja perustamaan siirtokunnan. Jean-François Robervalin johdolla ranskalaiset perustivat 1541 Stadaconan lähelle Charlesbourg-Royalin. Sinne muutti noin 150 siirtolaista, mutta ensimmäisenä talvena suhteet intiaaneihin heikkenivät, ja he surmasivat yli 30 siirtokunnan asukkaista. Seuraavana keväänä hengiinjääneet palasivat Ranskaan.Henriksson, s. 65–66. Englantilaiset eivät olleet paljoakaan kiinnittäneet huomiota Kanadaan, vaikka Cabot olikin käynyt rannikolla. Kuitenkin vuonna 1583 Humphrey Gilbert julisti nykyisen St. John’sin alueen kuuluvaksi Englannille.
Ranskalaiset aloittivat 1500-luvun puolivälissä Labradorin eteläosissa turkiskaupan intiaanien kanssa, ja vuosisadan lopulla rannikolla vieraili vuosittain useita kauppalaivoja.Henriksson, s. 70–72. Ranskalaiset myönsivät 1588 ensimmäisen turkiskaupan monopolin, ja tästä käynnistyi taistelu kaupan hallinnasta.Zimmerman, s. 829–830. Tadoussacista kehittyi merkittävä kauppakeskus, ja sinne suunniteltiin siirtokunnan perustamista. Ensimmäisistä alueella talvella 1600–1601 talvehtineista eurooppalaista selvisi vain viisi kuudestatoista. Pierre Dugua de Mons sai 1603 turkiskaupan yksinoikeuden. Hän perusti kesällä 1604 ensimmäisen tukikohdan Saint Croix’n saarelle (nykyisin Mainessa, Yhdysvalloissa). Keväällä 1605 tukikohta siirrettiin Nova Scotian Port Royaliin. Kumpikaan paikoista ei ollut kuitenkaan hyvä sisämaan turkiskaupan valvomiseen. Jatkossa turkiskauppaa valvottiin Stadaconan intiaanikylästä, jonka läheisyyteen Samuel de Champlain rakennutti 1608 muutaman puisen talon ja sitä ympäröivän paaluaidan intiaanien mallin mukaan. Paikasta kehittyi Quebecin kaupunki. Lakimies Marc Lescarbot oli asunut Port Royalissa, ja hänen vuonna 1609 julkaistuissa muistiinpanoissa mainittiin ensimmäisen kerran Uusi-Ranska.
thumb|Rupertinmaa Ranskalaiset hallitsivat turkiskauppaa käytännössä seuraavien vuosikymmenien ajan. Ranskalaiset perustivat Montrealin vuonna 1642, ja vuonna 1663 Ludvig XIV teki Uudesta-Ranskasta Ranskan siirtomaan.Encyclopædia Britannica. Tilanne muuttui, kun kaksi ranskalaista turkiskauppiasta Pierre-Esprit Radisson ja Médard des Groseilliers kertoivat briteille, että parhaat turkisalueet olivat Yläjärvestä länteen ja alueelle pääsisi helposti Hudsoninlahden kautta. Kaarle II perusti pian Hudson’s Bay Companyn ja antoi tälle yksinoikeuden Hudsoninlahden valuma-alueelle. Rupertinmaaksi kutsuttu alue käsitti noin 40 prosenttia nykyisestä Kanadasta, ja siihen kuului läntinen Quebec, luoteinen Ontario, Manitoba, suurin osa Saskatchewanista ja Albertasta sekä osia Luoteisterritorioista ja Nunavutista.
Ranska ei pitänyt Britannian aikeista valloittaa turkiskauppa ja perusti myös kauppapaikkoja sisämaahan. Britannia ja Ranska kävivät lukuisia taisteluita 1600- ja 1700-luvuilla sekä Euroopassa että Pohjois-Amerikassa. Kuningatar Annan sodan päättäneessä Utrechtin sopimuksessa 1713 Ranska joutui hyväksymään Britannian vaatimukset Hudsoninlahdesta ja Newfoundlandista ja antamaan Britannialle Acadien Cape Bretonin saarta lukuun ottamatta. Taistelut loppuivat muutamaksi vuosikymmeneksi, kunnes ne käynnistyivät jälleen 1754 ranskalaisten ja intiaanien sodassa, joka oli osa Euroopassa käytyä seitsenvuotista sotaa. Sotaonni kääntyi nopeasti briteille, kun he valtasivat Louisbourgin linnoituksen, joka sijaitsi strategisesti tärkeällä paikalla Saint Lawrencen lahden suulla. Quebecin taistelussa 1759 britit kukistivat ranskalaiset lopullisesti, ja Pariisin sopimuksessa 1763 Ranska joutui antamaan koko Kanadan Britannialle.
Britannian hallinta thumb|Ala-Kanada vihreällä ja Ylä-Kanada oranssilla. Brittiläisen Pohjois-Amerikan kuvernööri Guy Carleton antoi vuoden 1774 Quebec Actissä kanadanranskalaisile oikeuden omaan uskontoonsa ja hakea poliittisia tehtäviä sekä palautti ranskalaisen säädösoikeuden. Näin hän pystyi säilyttämään ranskalaisten uskollisuuden, ja Amerikan vallankumouksen (1775–1783) aikana suurin osa kanadanranskalaisista kieltäytyi tarttumasta aseisiin. Vallankumouksen jälkeen Kanadaan muutti noin 50 000 brittihallinnolle uskollista lojalistia, vaikkakin monet muuttajista olivat halvan maan perässä. Suurin osa saapui Nova Scotiaan ja New Brunswickiin. Noin 8 000 muutti Quebeciin, ja he muodostivat sen ensimmäisen merkittävän englanninkielisen vähemmistön.Zimmerman, s. 831.