В 1915—1920 гг. учился в Музыкальной академии и университете в Мюнхене, ученик Фридриха Клозе и Вальтера Курвуазье (композиция), Гуго Рёра (дирижирование), Бертольда Келлермана (фортепиано); практиковался как ассистент у Бруно Вальтера и Ганса Кнаппертсбуша. В 1924—1931 гг. работал оперным дирижёром в Аугсбурге. Ученик Пауля Хиндемита.
В 1933 году молодой блестящий пианист и композитор впервые посетил Эрец-Исраэль с концертами. Тогда он и поменял свою труднопроизносимую здесь фамилию на Бен-Хаим (по имени отца: Генрих — Хаим). Вернувшись в Германию, Пауль обнаружил на своем столе приглашение на собрание музыкантов Мюнхена. Внизу было напечатано: «Евреям вход запрещен» и приписка от руки: «Просьба прийти, несмотря на напечатанное». Молодой музыкант даже не распаковал чемоданы и некоторое время спустя снова приехал в Эрец-Исраэль, на этот раз — навсегда.
Поселившись в Израиле, активно работал как педагог, концертмейстер, дирижёр. Наибольшую творческую активность Бен-Хаим проявил как композитор. Ещё в 1930-х годах молодого репатрианта очаровали мелодии евреев — выходцев из Йемена, и Пауль Бен-Хаим стал основоположником «средиземноморского стиля» в академической музыке, сочетавшего в себе наряду с западными музыкальными формами элементы восточного, в основном йеменского, фольклора. Средиземноморский стиль стал главенствующим в 1950-е гг., заметными его представителями стали А.-У. Боскович и Марк Лаври.
В музыке Бен-Хаима преобладает пасторально-лирический элемент, однако в некоторых произведениях, главным образом на библейские темы (например «Гимн из пустыни», 1963), он достигает высокого драматизма. Бен-Хаим — автор двух симфоний военных лет (1940, 1945) и симфонии «Сладкоголосый псалмопевец Израиля» (1953); концертов для фортепиано (1949), скрипки (1960) и виолончели (1962) с оркестром; «Литургической кантаты» (1950); кантат «Видение пророка» (1959), «Три псалма» (1952) и «Каббалат шаббат» («Встреча субботы», 1967); большого числа песен, инструментальных миниатюр, камерных сочинений.
Среди учеников Бен-Хаима — Цви Авни, Ами Мааяни, Бенцион Оргад, Ноам Шериф, Элиаху Инбал и другие.