Il apprend le piano à partir de 4 ans et le saxophone à partir de 12 ans. Il découvre la flûte à 22 ans au conservatoire d'Oberlin (Ohio) et obtient un master's degree à la Manhattan School of Music.
Après avoir fait ses débuts professionnels en compagnie de Mongo Santamaria, il participe à plusieurs groupes jazzy dont Sauter-Finegan Orchestra (1956), Chico Hamilton Quintet (1956-58), Suite Thursday, le Duke Ellington Orchestra, Nat King Cole et Tony Bennett.
Voyageur, à la fin des années 1960, il découvre l'Inde, sa musique et sa spiritualité, par la méditation transcendantale. Il initie alors le thème inside, correspondant à un enregistrement de solo de flûte improvisée dans un haut lieu spirituel, le Taj Mahal en l'occurrence. Suivront les pyramides, les cathédrales, etc. Peu à peu, de l'Inde, il va se tourner vers la Chine, puis vers des expériences plus métissées.
Il est aussi saxophoniste et clarinettiste.
Discographie
En tant que leader
House of Horn (Dot, 1957)
Plenty of Horn (Dot, 1958)
Impressions! (World Pacific, 1959)
Something Blue, (1960)
The Jazz Years, (1961)
The Sound of Paul Horn, (1961)
Profile of a Jazz Musician, (1962)
In India & Kashmir, (1968)
Inside ou Inside the Taj Mahal (1968)
July 9-10, (1973)
Visions, (1974)
Altura Do Sol ou The Altitude of the Sun, (1975, avec Egberto Gismonti)