Пол Бентелло родился 16 января 1974 года в городе Амарилло, штат Техас. Детство провёл в городке Тьюлия, учился в одной школе с другим известным бойцом Эваном Таннером.
В школьные годы играл в бейсбол и футбол, а после выпуска начал серьёзно заниматься тхэквондо. За своеобразную манеру нанесения ударов ногами по голове получил прозвище «Охотник за головами» .Дебютировал в смешанных единоборствах на профессиональном уровне в апреле 1997 года — провёл сразу три боя за один вечер, в двух выиграл, но в третьем встретился с Эваном Таннером и проиграл удушающим приёмом сзади. Затем продолжил выступать в различных местных техасских промоушенах, часто выигрывал, но были и поражения, в частности поражение сдачей от Дэна Северна.
В 2000 году Бентелло участвовал в турнире на выбывание IFC Warriors Challenge, где опять же победил в четвертьфинале и полуфинале, но в решающем поединке уступил Гэну Макги. Начиная с 2001 года активно сотрудничал с бойцовской организацией King of the Cage, дважды неудачно оспаривал титул чемпиона в тяжёлом весе, проиграл титульные поединки Рикко Родригесу и Бобби Хоффману.
В ноябре 2003 года в матче-реванше с Бобби Хоффманом с третьей попытки наконец завоевал чемпионский пояс.Имея в послужном списке 19 побед и 8 поражений, в 2005 году Бентелло привлёк к себе внимание крупнейшего американского промоушена Ultimate Fighting Championship и вскоре одержал здесь две громкие победы, нокаутом над Джастином Эйлерсом и болевым приёмом над Кевином Джорданом. Благодаря череде удачных выступлений удостоился права оспорить титул чемпиона UFC в тяжёлой весовой категории, который на тот момент принадлежал представителю Белоруссии Андрею Орловскому.
В итоге Орловский нокаутировал его за 15 секунд, и этот бой оказался самым коротким титульным боем за всю историю организации. После сокрушительного поражения от Орловского Пол Бентелло одержал в UFC ещё одну победу, но затем всё равно покинул промоушен.
В период 2006—2007 годов Бентелло выступал в другой крупной американской организации Strikeforce, выиграл здесь три поединка подряд и получил титульный бой с голландцем Алистаром Оверимом, которому в итоге всё же уступил. Позже принял участие в серии турниров Affliction, где отметился победами над канадцем Гари Гудриджем и российским самбистом Кириллом Сидельниковым.
В 2009 году вернулся в UFC, но дважды подряд потерпел поражение, сначала решением большинства судей от представителя Нидерландов Стефана Стрюве, затем сдачей от представителя Франции Чейка Конго.
В 2010 году дрался в менее престижных промоушенах, таких как Shark Fights, Powerhouse World Promotions, Nemesis Fighting. Оспаривал титул чемпиона PWP в тяжёлом весе, но в концовке второго раунда был нокаутирован Тимом Сильвией. Единогласным решением судей взял верх над американский бойцом-ветераном Керри Шоллом.
В 2011 году провёл один бой в Bellator, проиграв единогласным решением действующему чемпиону организации Коулу Конраду, хотя их бой не имел статус титульного.Пол Бентелло трижды дрался на турнирах в России, в частности в июле 2016 года на турнире ACB в Сочи встречался с россиянином Денисом Гольцовым, в первом раунде пропустил сильный удар ногой в голову и проиграл нокаутом.