Gary Brooker, né en 1945, débute les cours de piano à 11 ans. Son professeur constate qu’il préfère plutôt jouer du Ray Charles que du classique. Compréhensif, il enrichira ses cours avec des morceaux du grand chanteur américain. Brooker en tire la conclusion que Bach et Ray Charles ont peut-être quelque chose en commun. A la fin des années 50, Gary Brooker forme The Paramounts, avec Barry J. Wilson, Robin Trower à la guitare, et un autre musicien destiné à rejoindre Procol Harum plusieurs années après sa formation : le bassiste Chris Copping. Les Paramounts jouent essentiellement du rhythm 'n’ blues, un genre alors très en vogue, beaucoup de reprises, enregistre quelques singles et un album, et tourne même avec les Rolling Stones.
En 1966, Gary Brooker quitte The Paramounts en pleine désagrégation. Lassé de ce genre musical, il cherche un projet neuf. Il rencontre alors Keith Reid, qui désire faire connaître les poèmes qu'il écrit et laisse à Gary l'un de ses textes. Le lendemain, il lui téléphone pour lui demander ce qu'il en a pensé. Gary lui répond qu'il a déjà posé une chanson sur ses mots et qu'il aimerait lui faire entendre. Le tandem Brooker-Reid, signataire de la plus grande partie des morceaux du futur Procol Harum, vient de naître. Dans un premier temps, les deux jeunes hommes ne pensent pas enregistrer leurs chansons eux-mêmes. Ils les proposent à d'autres artistes tels que Dusty Springfield ou les Beach Boys, mais tous refusent. Arrivés à la conclusion qu'ils seront les seuls à vouloir jouer leurs morceaux, Brooker et Reid recrutent des musiciens : Robin Trower reprend la guitare, B.J. Wilson la batterie, et David Knights les rejoint à la basse. Une petite annonce passée dans le Melody Maker par un organiste intrigue Brooker. C'est ainsi qu'il rencontre Matthew Fisher, très imprégné par la musique baroque, et qui joue de l'orgue et du clavecin. A l'avenir, Fisher signera quelques compositions, parfois avec Brooker. Il est recruté comme membre à part entière du groupe, tout comme Keith Reid, bien que ce dernier ne joue d'aucun instrument. Ami du groupe, l'animateur radio Guy Stevens téléphone à Brooker pour lui suggérer une idée de nom : il vient d'apprendre qu'un chat de son quartier porte un pedigree du nom de Procol Harum, ce nom étrange plaît au groupe qui l'adopte aussitôt.
Les répétitions commencent. Gary Brooker interprète un nouveau morceau, David Knights : « c'est un tube ! », Brooker : « non, juste une de nos chansons… ». Cette chanson s'appelle « A Whiter Shade of Pale », dont les cinq premiers accords et la ligne de basse descendante sont inspirés de l’air sur un accord de sol de la suite en ré majeur de Bach (BWV 1068). Produite par Denny Cordell (The Moody Blues) qui veut un « slow » dans la lignée de « When A Man Loves A Woman » de Percy Sledge, elle sort en single, devient un tube immense en France (il y est d’ailleurs le premier 45t étranger à inclure seulement deux titres), puis au Royaume-Uni, et enfin dans le monde entier. C’est l’été 1967, Procol Harum vient d’écrire le majestueux slow planétaire et inoxydable du fameux «summer of love». Il est suivi en octobre d’un autre hit, « Homburg », tout aussi cérémonieux.
Enthousiaste, le groupe sort un album éponyme avant la fin de l'année, dont la première édition ne contient pas les deux hits. Le premier quintette Procol Harum ne manque pas d'originalité pour son époque. La présence de Keith Reid, parolier officiel, est alors une première. Il pose avec les musiciens sur toutes les photos. La présence de deux claviers constitue également une nouveauté. Brooker ne quitte jamais le piano, et Fisher ne joue que de l'orgue ou du clavecin. Les deux instruments peuvent être joués soit en tant qu'instrument baroque, soit avec un style blues. Ils s'enrichissent régulièrement de contrepoints. Le jeu de batterie de Wilson est excellent et typique de l'époque, très rapide, syncopé et épais. La guitare électrique est très marquée par les sixties, elle tente de sonner Hendrix avec peu de conviction. Les compositions de Procol Harum sont résolument pop, avec cette influence classique qui assurera le succès à d'autres groupes de l'époque, de Iron Butterfly aux Moody Blues.