Paul Grégoire was born in Viauville, Montreal, to J. Albert Grégoire and Marie Lavoie, but his family moved to Verdun shortly after his birth. He had two younger brothers, but his parents later adopted nine of his cousins. He studied at the Minor Seminary of St. Thérèse in Blainville from 1925 to 1933, and then at the Major Seminary of Montréal from 1933 to 1937, where he obtained a licentiate in theology. He was ordained a priest on May 22, 1937, and then taught at St. Thérèse in Blanville until 1939. From 1939 to 1942, he furthered his studies at the University of Montréal, where he earned doctorates in philosophy and history, licentiate in letters, and diploma in pedagogy.