Син ірландців-католиків Гаттона Гібсона та Ен Райлі Гібсон, яка народилася в парафії Колм-Кіллє графства Лонгфорд, Ірландія. Його бабця по батькові Ева Майлот була австралійською оперною співачкою. Мел народився у місті Пікскілл (округ Вестчестер, штат Нью-Йорк) і був шостим з одинадцяти дітей. Один із молодших братів Мела, Донал, також актор.
Імена пов'язані парафією Колумкіл (св. Колумба) в окрузі Лонгфорд, де народилася і виросла його мати. Перше ім'я Гібсона — Мел — походить від імені ірландського святого 5 століття, засновника дієцезії (єпархії) з центром у місті Ардах, до якої входило майже все вказане графство, друге ім'я — Колм-Кіллє — також походить від імені ірландського святого 5 століття, ірландського місіонера у Шотландії.
Хоча за народженням є громадянином США, Гаттон Гібсон перевіз свою родину до Австралії, а саме Сіднею в 1968, після перемоги у судовій справі проти залізничної компанії New York Central Railroad, пов'язаній із його каліцтвом на колії. Цей переїзд був протестом проти війни у В'єтнамі, на яку міг бути призваний старший брат Мела. Переїзд відбувся також тому, що Гаттон, набожний католик-традиціоналіст, був упевнений, що зміни в американському суспільстві, що відбувалися у 60-і роки, були аморальними.