Ce natif de Québec, fils d'un ancien maire de la Vieille capitale (Joseph-Ernest Grégoire, 1934-1938), étudie à l'Université Laval et travaille comme journaliste avant de se lancer dans l'aventure politique, au début des années 60. Gilles Grégoire se fait d'abord élire à Ottawa sous la bannière du Crédit social (1962, 1963), puis du Ralliement créditiste (1965). En 1966, il s'implique au sein du Ralliement national (RN), une formation politique de centre droit oeuvrant sur la scène provinciale qui milite pour la souveraineté du Québec. Le RN obtient 3,2% des voix lors des élections générales de l'été 1966, mais ne fait élire aucun député. Grégoire en devient le président par la suite. Deux ans plus tard, il est aux premières loges pour assister à la naissance du Parti québécois (PQ), formation qui voit le jour avec la fusion du RN et du Mouvement souveraineté-association de René Lévesque. Vice-président du PQ de 1968 à 1972, Grégoire fait son entrée à l'Assemblée nationale en 1976 comme député de la circonscription de Frontenac. Il est réélu en 1981 mais son mandat, qu'il termine comme député indépendant, est terni par une histoire de moeurs.