Le fort Frontenac est situé à l'embouchure de la rivière Cataraqui (Cataroque), à l'emplacement actuel de la ville de Kingston, à l'extrémité nord-est du lac Ontario, dans la province de l'Ontario du Canada actuel, dans la partie occidentale de la Nouvelle-France appelée alors le Pays-d'en-Haut.
D'abord dénommé fort Cataracoui ou Kataracouy, il ne prit le nom de Frontenac qu'ultérieurement. Le nom Cataraqui est issu du mot iroquois Katarokewen qui signifie « terre de glaise tirée hors de l’eau ».
Histoire thumb|right|upright|Plan du fort Frontenac, 1685. thumb|Le fort Frontenac à l'époque de la Nouvelle-France. La construction du fort Frontenac débuta en , sur ordre de Louis de Buade de Frontenac (gouverneur de la Nouvelle-France), lors de négociations entre une délégation (les Onontchataronons) des Cinq-Nations d'Iroquois et lui. Ce fort devait protéger Ville-Marie (Montréal) qui était à cinq jours de canot et favoriser l'expansion de la colonie canadienne, par les Français, afin d'établir des postes de traite de fourrures à l'intérieur de l'Amérique du Nord, dans la région des Grands Lacs et la vallée de l'OhioChrétien Le Clercq, Premier établissement de la Foy, tome 2, p. 110-117..
Le comte de Frontenac arrive à Québec en . Après quelques discussions avec l'intendant Talon et le gouverneur sortant, Daniel de Rémy de Courcelles, il décide de construire à ses frais ( pour son établissement et sa garnison) un avant-poste sur le lac Ontario. Le , il arrive donc à l'embouchure de la rivière Cataracoui, accompagné de son interprète et riche marchand Charles Le Moyne, sieur de Longueuil et de Châteauguay, et d'environ réguliers du régiment de Carignan-Salières, pour rencontrer les chefs des cinq nations iroquoises pour les encourager à faire le commerce et faire la paix avec les Français. Pendant que les groupes se rencontrent et s'échangent des cadeaux, les hommes de Frontenac, sous les ordres de l'ingénieur militaire Hugues Randin, construisent à la hâte une palissade en bois sur la pointe de terre, près d'une baie abritée. C'est à partir de ce moment que le fort Frontenac est créé. C'est donc l'ingénieur Hugues Randin qui fut l'architecte de ce fort. Il dressa les plans du fort et en dirigea la construction. Le fort est achevé le et palissadé le . Trois ans plus tard, les Français le démantèleront pour le rebâtir en pierre.
Il s'agissait des prémices d'une entreprise de commerce de peaux et de fourrures. Le centre de traite était également une mission religieuse. L'emplacement stratégique du fort garantissait le monopole du commerce dans la région. Frontenac participe lui-même à la traite des fourrures, en se rendant chaque année au fort avec une flottille de canots chargés de marchandises à troquer avec les Amérindiens.
Les débuts de l'établissement
Le fort s'appelait à ses débuts fort Cataraqui (aussi Catarakoui, Cataracoui) qui fut rebaptisé fort Frontenac. La Salle obtient donc le fort Il obtenait la propriété de Il changea alors le nom de ce fort pour flatter son protecteur, le gouverneur de Frontenac.
Le but du fort Frontenac était de contrôler le lucratif commerce des fourrures dans le bassin des Grands Lacs à l'ouest et dans le Bouclier canadien au nord et d'être le lien avec les avant-postes français qui seraient créées dans les Grands Lacs et les régions du haut du Mississippi. Le fort était censé être un rempart contre les Anglais et les Hollandais qui étaient en concurrence avec les Français pour le contrôle du commerce des fourrures. Une autre fonction du fort était la mise à la disposition des fournitures et d'envoyer des renforts aux autres installations françaises sur les Grands Lacs et dans la vallée de l'Ohio, vers le sud. De plus, Frontenac espérait que le fort l'aiderait à atteindre ses propres ambitions d'affaires.
René-Robert Cavelier de La Salle est donc le premier administrateur et commandant du fort. En même temps, il y installe une petite communauté de récollets dont le premier supérieur est le Père Gabriel de la Ribourde. Au printemps de 1676, Louis Hennepin est envoyé au fort Cataracoui afin de remplacer le Père Léonard Duchesne et il assiste aux travaux de fortification que fait faire La Salle : Avec l'aide de son confrère Luc Buisset, Hennepin construit entre 1676-1678 une chapelle et une résidence missionnaire, fréquentée bientôt par de nombreux Iroquois.
À partir de 1676, La Salle fit remplacer les palissades en bois par de la pierre, et un bastion en pierre fut rajouté selon une description écrite du fort au :
Durant la décennie suivante, des améliorations sont apportées au fort : agrandissement des bastions, ajout d'habitations. En 1685, le fort est entouré d'un petit village composé de civils, d'Amérindiens et de religieux récollets. La Salle avait aussi fait venir des animaux domestiques dans l'espoir d'inciter des colons à venir s'installer près de cet avant-poste à Cataraqui. Des terres sont défrichées pour permettre l'agriculture, ainsi que l'élevage du bœuf, du porc et de la volaille.
Étant donné que La Salle était un explorateur avant tout, il embaucha comme commis François Dauphin de la Forest pour administrer le fort Cataracoui pendant ses nombreux voyages. Il le charge d'agir comme son procureur et d'assurer le commandement avec le titre de major. Ainsi une petite colonie française s'établissait dans les environs, près du village amérindien. Le troc de nourriture , qui nait de l'association entre le poste de traite et le village amérindien faisait partie intégrante de la vie quotidienne. Ainsi les Iroquois, en période de paix, pourvoient le fort Frontenac , en échange d'aiguilles, de couteaux, de poudres, de balles et d'autres produits européens.
Afin de tenir les Anglais hors de cette région, l'intendant Jean Talon encourage l'organisation d'une série d'expéditions. C'est ainsi que le , Cavelier de La Salle part, depuis le fort Frontenac, pour établir une route reliant la Nouvelle-France au golfe du Mexique. Ce fort servira donc comme base pratique pour les explorations vers l'intérieur de l'Amérique du Nord.
Les guerres iroquoises
Les rivalités concernant le commerce des fourrures ont abouti aux guerres iroquoises. Les Français et les Iroquois (encouragés par les Anglais et les Hollandais) n'ont jamais été en très bon termes, et ce depuis Samuel de Champlain(Shampeline), le . Un traité de paix fut signé en 1667, après l'arrivée du régiment de Carignan-Salières, mais la guerre fut de nouveau déclarée dans les années 1680, et cette nouvelle guerre affecta le fort Frontenac.
Le , Madeleine de Roybon d'Allonne prête à l'explorateur René-Robert Cavalier de La Salle. En retour et en fief de seigneurie, celui-ci criblé de dettes lui concède une maison et une terre à un endroit nommé Tonequinion (aujourd'hui Collins Bay). Au cours de la guerre contre les Iroquois (1686-1701), elle est capturée. Au début d', elle perd son commerce de pelleteries, ses bâtiments et ses terres.
En 1682, l'un des plus redoutables chefs Onontagués, Chaudière Noire, pilla le fort Cataracoui, et il l'attaqua de nouveau en août et .
vignette|Séance de négociation entre le gouverneur de la Barre et le chef iroquois La Grangula en 1684.
En 1687, le gouverneur Denonville a remplacé La Barre à la suite de la débâcle de 1684. Voulant briser la résistance iroquoise, il envoie ses troupes en expédition dans les villages avoisinant le fort afin de capturer par traîtrise une cinquantaine d'Iroquois afin de les déporter en France pour servir de galériens. Lahontan, qui est témoin de cette opération, est puni pour s'être opposé à la torture d'un Iroquois qu'il connaissait :
Les troupes de Denonville et ses alliés hurons passent ensuite à l'attaque contre les Iroquois Sénécas, au sud du lac Ontario. Ainsi, en 1688, les relations avec les Iroquois se détériorent. En représailles pour ces incidents et d'autres « tricheries », un groupe de guerriers attaqua un certain nombre d'établissements français, notamment le fort Frontenac. Le fort et l'établissement à Cataraqui sont assiégés par les Iroquois pendant deux mois en 1688. Bien que le fort n'ait pas été détruit, l'établissement est dévasté et les Iroquois détinrent en captivité trois soldats et Madeleine de Roybon d'Alone (la maîtresse de La Salle). De plus, 93 défenseurs moururent durant ce long siège, dont la plupart du scorbut. (On pense que ce sont leurs restes qu'on a découverts sur le site, lors de fouilles à l'été 1987).
En 1689, après le massacre de Lachine par les Iroquois, le fort est partiellement détruit sur ordre de Denonville et, en 1691, le nouveau gouverneur Frontenac confie à Pierre Legardeur de Repentigny la mission d'abandonner le fort et de rapatrier sa garnison à Québec, car son éloignement empêchait une bonne défense et un ravitaillement adéquat.
Le gouverneur de New York, Benjamin Fletcher, convoque à Albany le un Grand Conseil iroquois et insiste pour que les Iroquois n'autorisent pas les Français à reconstruire Cataracoui : Iroquoisie 1688-1701, tome 4..
En 1695, Frontenac ordonne la reconstruction du fort, malgré la ferme opposition de l'intendant Champigny, qui a l'ascendant de la Couronne. À ce sujet, Frontenac admet à Lagny, son ami et intendant du commerce en France, que même si les ordres émis par Pontchartrain de ne pas rétablir le fort lui étaient parvenus à temps, il les aurait ignorés, considérant que dans le contexte de la guerre intercoloniale, il était plus à même de prendre les meilleures décisions que la haute administration coloniale, à VersaillesArchives Coloniale, Série C11A, vol. 13, f. 322-329.. Le fort reconstruit fut renforcé par les 300 hommes de troupes de François Charles de Bourlamaque et par 160 habitants.
En 1696, François DeJordy-Moreau, un ami de Frontenac, devient le commandant du fort. Il est remplacé par Louis de Laporte sieur de Louvigny le . Cependant durant l'hiver, ce dernier fit illégalement le commerce des fourrures et fut arrêté et destitué de son poste, car il avait enfreint l'édit de 1696 qui interdisait tout commerce dans les postes de l'Ouest.
La Grande paix de Montréal est signée le , avec la France et les peuples amérindiens, dont les Iroquois, grâce aux efforts de diplomatie du grand chef huron Kondiaronk.
La guerre de Sept Ans
thumb|Le fort Frontenac durant la guerre de Sept Ans. Au début des années 1700, les Français augmentèrent les capacités défensives du fort par l'ajout de nouvelles armes, la construction de nouvelles casernes et l'augmentation de la garnison. Ces améliorations, toutefois, seront vaines.
Au cours des années 1720, les commandants du fort Frontenac, Jacques-Hugues Péan de Livaudière, Pierre-Jacques Payen de Noyan et René Le Gardeur de Beauvais, renforcèrent les liaisons entre Montréal, le fort Frontenac et le fort Michilimakinac situé dans le Pays-d'en-Haut dans la région des Grands LacsDictionnaire biographique du Canada. L'ensemble des structures du fort sont construites en pierre et desservent la plupart des besoins de la population.
En 1744, devant les menaces de guerre, le fort Frontenac est renforcé et devient un important dépôt d'approvisionnement pour les postes intérieurs nouvellement fondés. Les bâtiments désuets sont améliorés. Des ajouts militaires sont construits pour protéger le fort. En 1754, deux marchands ont des entrepôts et des quais près du fort. L'agglomération se démarque commercialement des autres villes à cause de son commerce d'expédition. thumb|gauche|upright|Uniforme de l'infanterie de Guyenne en 1757 Arrivée du capitaine Pierre Pouchot, avec le Régiment de Béarn, et du Régiment de Guyenne en . Cet ingénieur de l'armée aide à l'amélioration des défenses du fort.