根据考古研究（英语：Archaeology of the Americas）及遗传学分析（英语：Genetic history of indigenous peoples of the Americas），至少在2.45万年前育空北部即有人类活动，而南安大略的人类活动可以追溯到公元前7500年。旧克罗平地（英语：Old Crow Flats）和蓝鱼洞穴（英语：Bluefish Caves）遗迹是加拿大境内最古老的人类居住地。原住民社会的特点包括有永久居住点、农业耕种、复杂的社会等级和贸易网络。一部分原住民文明在欧洲殖民者抵达加拿大前已瓦解，如今只能通过考古发掘研究那些文明。
1583年，英国人汉弗莱·吉尔伯特爵士在如今纽芬兰的圣约翰斯建立定居点，并宣称这是英国在北美的第一块殖民地。之后法国探险家萨缪尔·德·让普兰分别在1605年于新斯科舍省的皇家港（英语：Port Royal, Annapolis County, Nova Scotia）和在1608年于魁北克省魁北克市建立北美最早的欧洲人永久定居点。在新法兰西的范围内，法裔加拿大人开始沿着圣劳伦斯河一带扩张，阿卡迪亚人也开始在大西洋省份定居，而传教士和皮毛商人（英语：Coureur des bois）开始探索五大湖、哈德森湾及密西西比河流域一带。后来在17世纪中叶，为了争夺皮毛交易（英语：North American fur trade）的控制权，阿尔冈金部落和易洛魁部落分别在英国、荷兰和法国的支持下发生河狸战争（英语：Beaver Wars）。
出于对问责政府的渴求，加拿大人发动1837年起义。叛乱被平息之后到加拿大调查的达勒姆勋爵建立一篇报告，《英属北美事务分析（英语：Report on the Affairs of British North America）》。报告建议把现任政府改为问责制政府，并支持同化法裔加拿大人，使其接受英国语言及文化。英国政府接纳达勒姆勋爵在报告中的建议，并颁布1840年联合法案（英语：Act of Union 1840），重新将上下加拿大合并成立加拿大省。 1849年，代表所有英属北美的责任政府建立。1846年，英美签定俄勒冈条约，确定美国和英属北美在西部以北纬49度为界。这一条约解决长久以来英属北美与美国的边境争端，也为英国建立温哥华岛殖民地和不列颠哥伦比亚殖民地铺平道路。
联邦的组成及扩张
经过数次立宪会议之后，《1867年宪法法令》于1867年7月1日通过，加拿大省、新不伦瑞克省、新斯科舍省三个英属北美殖民地组成加拿大联邦。加拿大获得罗伯特领地和西北部地区（英语：North-Western Territory）的控制权，并将两者合并成西北地区，这一举动促使该地区的原住民梅蒂人在1870年7月发动红河起义（英语：Red River Rebellion）并建立从西北地区分离出的曼尼托巴省。