En 1992, en réponse aux démarches politiques des organismes des Premières Nations et Inuit, le gouvernement canadien a développé la stratégie « Les chemins de la réussite » et a signé des ententes de cogestion dans le but de favoriser la participation active des communautés de Premières Nations au Canada dans la prestation de services en matière de formation et de perfectionnement de leur main-d’œuvre. En vertu d’une entente de cogestion avec les autorités fédérales canadiennes, les Premières Nations du Québec ont formé la Commission autochtone de gestion régionale du Québec (CAGRQ). Le mandat de la Commission consistait principalement à soutenir le développement des organismes afin d’offrir formation et perfectionnement à la main-d’œuvre des Premières Nations du Québec. Cette entente de quatre ans a produit des résultats très positifs et a conduit à de nouvelles ententes.

En 1996, les Premières Nations du Québec et Ressources humaines et développement Canada ont signé un nouveau type d’entente. Les Ententes bilatérales régionales (EBR) avaient pour objectif spécifique de transférer aux divers regroupements représentant les Premières Nations, les Métis et les Inuit tous les pouvoirs nécessaires pour assumer l’ensemble des responsabilités en matière de formation et de perfectionnement de leur main-d’œuvre respective. Parmi ces ententes figurait l’entente qui est entrée en vigueur sous l’égide de l’APNQL. L’adoption de la résolution 3/1996 des Chefs a mené à la création de la CDRHPNQ.

En 1999, la Stratégie de développement des ressources humaines autochtones de RHDC incluait officiellement une composante urbaine nommée « Stratégie urbaine ».

En 2001, l’APNQL a mandaté la CDRHPNQ pour établir une structure de services assurant à tous les membres des Premières Nations vivant hors réserve des services justes et équitables en matière d’emploi et de formation. La résolution 16/2001 des Chefs demandait en outre que la CDRHPNQ révise certains mécanismes financiers et de prise de décision de la Stratégie urbaine en collaboration avec Le Regroupement des Centres d’amitié Autochtones du Québec (RCAAQ) et Femmes Autochtones du Québec (FAQ).

En 2007, aussitôt que RHDCC a annoncé la fin envisagée de la Stratégie de développement des ressources humaines autochtones (SDRHA), la CDRHPNQ a pris des mesures afin d’influencer le contenu du nouveau programme qui la remplacerait. Dès les premières consultations où des soumissions pour l’offre de services en emploi destinés aux Autochtones ont été examinées, la CDRHPNQ ainsi que les autres Premières Nations signataires d’entente ont toutes rejeté l’approche proposée, réitéré leurs revendications historiques en matière de financement et de ressources humaines, et demandé la parité avec les ententes Canada-Province relatives au marché du travail. Soutenue par l’Assemblée des Chefs, la CDRHPNQ a poursuivi ses actions dans les enceintes politiques et répété à plusieurs reprises son message. Depuis, le gouvernement a abandonné l’idée d’utiliser des soumissions, mais exige toujours que le signataire d’entente élabore un plan d’affaires stratégique quinquennal pour obtenir l’approbation ministérielle préalable à la ratification des ententes administratives.

À l’automne 2009, l’actuelle Stratégie de formation pour les compétences et l’emploi destinée aux Autochtones (SFCEA) était annoncée. L’assemblée des membres de la CDRHPNQ a approuvé le plan d’affaire stratégique 2010-2015. RHDCC n’ayant pas finalisé les lignes directrices financières et opérationnelles de la SFCEA au 1er avril 2010, les signataires d’ententes, dont la CDRHPNQ, n’ont commencé à offrir des services dans le cadre de la SFCEA qu’à partir du 1er octobre 2010.