Gaggi fue hijo de Angelo y Mary Gaggi, fue el menor de tres hijos. Tuvo una hermana, Marie, y un hermano conocido como "Roy". Su padre emigró a los Estados Unidos desde Palermo, Sicilia, Italia y administró una barbería en el Lower East Side de Manhattan. Mary trabajó como costurera hasta el nacimiento de Gaggi.^[1]​

Gaggi abandonó la escuela en el octavo grado y ayudó a su padre en el negocio. También trabajaba distribuyendo flores y el dinero que ganaba en ello lo utilizaba para apostar. Fue a esa edad que conoció la rentabilidad de la usura a los apostadores.^[2]​ Cuando era un adolescente, su familia se mudó a Nueva Jersey luego de comprar una pequeña granja. Cuando cumplió 17 años en 1942, intentó unirse al Ejército pero fue rechazado por miope. En 1943, su familia abandonó la granja y se mudó al barrio de Bath Beach en Brooklyn. Su padre Angelo volvió a trabajar como barbero mientras su madre y su hermana trabajaban en una fabrica textil. Dado de baja del Ejército luego de una herida, Roy vendía dispensadores de maní a los bares.^[3]​

Luego de regresar a Nueva York, Gaggi decidió involucrarse en actividades criminales. El primo de su padre era el mafioso Frank Scalise, un miembro fundador de la familia criminal Gambino. Scalise ayudó a Gaggi a obtener un trabajo en un muelle de camiones donde rápidamente llegó a ser supervisor. Eventualmente Scalise le permitía ser un "empleado fantasma", alguien que recibía un sueldo pero no realizaba ningún trabajo. Gaggi entonces podía dedicarse a la usura en los bares de Brooklyn y las salas de billar. Este trabajo fantasma también le permitía reportar un ingreso legítimo y pagar impuestos a la IRS evitando que se le investigue por evasión de impuestos.^[4]​