Брак и фактические родственные отношения с Карло Гамбино стали ступеньками на пути Кастеллано к вершине криминальной семьи. Помимо того, что Гамбино был двоюродным братом, он женился на сестре Кастеллано, Кэтрин. По мере того как Карло продвигался по карьерной лестнице, Пол поднимался вместе с ним, служа в годы славы Карло его самым доверенным капо. Когда в середине 1970-х здоровье Гамбино пошатнулось, Кастеллано стал альтер-эго дона Карло и исполняющим обязанности босса семьи, а затем был официально провозглашен полноправным крестным отцом. Его доминирующая позиция в мафии и внушительный рост в шесть футов два дюйма позволили ему получить комплиментарное прозвище «Большой Пол».

Читатель Wall Street Journal и финансовых журналов, Кастеллано представлял себя бизнесменом и примирителем семьи, эквивалентным генеральному директору многопрофильной корпорации. Его легальный доход для целей налоговой службы складывался из «инвестиций» в мясокомбинаты и птицефабрики, а также в строительные компании, зарегистрированные на имена его сыновей и других родственников. Косметические усилия по маскировке под эрудированного бизнесмена произвели впечатление на одного из его ровесников по преступному миру, «Толстого Тони» Салерно. На одной из встреч, где присутствовали члены Дженовезе и Гамбино, Сальваторе «Сэмми Бык» Гравано услышал от Салерно редкий для мафии комплимент: «Пол, ты так красиво говоришь. Хотел бы я так говорить».

Невидимая власть Кастеллано явно распространялась на мир легального бизнеса, где руководители были осведомлены о власти семьи Гамбино над профсоюзами и ее тайных интересах в сетях супермаркетов Key и Waldbaum в Нью-Йорке. Паскуале «Пэт» или «Пэтси» Конте, капо Гамбино, искушенный в торговле наркотиками, входил в совет директоров Key Foods и имел властный голос при принятии решений о том, какие продукты будут продаваться в кооперативной сети. На вопрос агентов президентской комиссии, почему он отдает предпочтение продукции компаний Кастеллано, Айра Вальдбаум, основной владелец Waldbaum's, ответил, что «принимать меры» против организованной преступности — обязанность правоохранительных органов, а не бизнесменов. «Не забывайте, что у меня есть жена и дети», — сказал Вальдбаум.

Компания Dial Meat Purveyors, возглавляемая сыновьями Кастеллано, Полом-младшим и Джозефом, была основным поставщиком птицы и мяса в Нью-Йорке для более чем трехсот независимых розничных мясных лавок и многих супермаркетов. Благодаря тайным соглашениям с чиновниками Объединенного профсоюза работников пищевой и коммерческой промышленности Большой Пол мог прерывать поставки и разжигать трудовые проблемы в магазинах, которые не принимали его продукцию по установленным им ценам.

Самым ярким признаком уважения к Кастеллано со стороны крупного бизнеса стало обращение к нему национального поставщика мяса птицы Фрэнка Пердью. Пердью, чья телевизионная реклама его компании принесла ему национальное признание, в 1981 году признался ФБР, что как минимум дважды напрямую обращался за помощью к Кастеллано. В первый раз он поинтересовался, сможет ли Кастеллано сорвать попытки связанного с мафией Объединенного профсоюза работников пищевой и коммерческой промышленности организовать его главный перерабатывающий завод в Аккомаке, штат Вирджиния. Второй проблемой, которую, по мнению Пердью, мог бы решить Кастеллано, была его неспособность поставлять своих цыплят во многие сетевые супермаркеты в огромном нью-йоркском регионе.

Пердью так и не уточнил у ФБР, какую помощь предложил или оказал Кастеллано. Сначала, по его словам, он связался с Кастеллано из-за его опыта как инвестора в говядину, птицу и оптовые продовольственные компании в городе. На вопрос агента «Отряда Гамбино» Джозефа Ф. О'Брайена о том, почему он выбрал именно Кастеллано, а не представителей супермаркетов и мясного бизнеса, Пердью с громким гоготом ответил: «Почему? Потому что он — крестный отец».

Позже производитель курятины пояснил следователям из президентской комиссии по установлению фактов, что он обратился к Кастеллано, потому что тот, как известно, «имеет длинные щупальца как фигура организованной преступности». Да, мафия и мафия».

С первого дня пребывания на посту босса Гамбино Кастеллано превозносил свои исполнительные способности. В 1976 году он договорился со своим подчиненным, Аниелло Деллакроче, о контроле и распределении доходов банды. Все преступления «белых воротничков» — махинации на торгах, коррупция в профсоюзах, политические взятки, финансовые махинации — оставались в сфере влияния Большого Пола. Деллакроче сохранил за собой более традиционные и жестокие виды рэкета — ростовщичество, азартные игры и угоны. Но Кастеллано, как верховный босс, жадно требовал свою долю от добычи, собранной бандами Деллакроче.

В светящемся автопортрете Кастеллано была и жестокая, залитая кровью сторона. Прежде чем заняться «белыми воротничками», Кастеллано организовывал чрезвычайно прибыльные азартные игры, ростовщичество, угон автомобилей и вымогательство. И, разумеется, как босс он получал наибольшую долю от этих предприятий, даже если больше не играл значительной роли в их управлении. Он также подбирал опытных убийц внутри и вне семьи для выполнения необходимой грязной работы, заказных убийств, чтобы поддерживать свой контроль. Самым известным киллером был Рой ДеМео, который в 1970-х и начале 80-х годов возглавлял отряд, в котором, по данным федеральных и городских властей, погибло не менее семидесяти пяти человек. Джин Мастейн и Джерри Капеци в своей книге «Машина убийств» называют более двухсот человек.

Большинство жертв ДеМео так и не были найдены. По словам информаторов, его бригада использовала бруклинскую квартиру в качестве скотобойни, где трупы обескровливали в ванной, расчленяли в гостиной и упаковывали в картонные коробки. Затем частные мусоровозы выбрасывали части тел на свалки. Подобно тому, как ранее Коза Ностра использовала еврейских палачей в Murder Inc., Кастеллано видел маскировочную ценность в найме убийц, которые не были бы идентифицированы как мафиози. Одним из отрядов смерти, который он набрал, была банда этнических ирландских психопатов из района Адской кухни. Эти садисты, прозванные детективом «Вести», специализировались на том, что забивали жертв до смерти и избавлялись от них через очистные сооружения на острове Уордс в Ист-Ривер.