Cutolo was born in Ottaviano, a municipality in the hinterland of Naples, in a family without ties in the Camorra. His fatherless youth was spent in a close-knit Catholic environment. His father was an agricultural labourer who for years tilled a field as a sharecropper as a means to support his family. While still a child, the landowner told Cutolo's father that the following year the field would be used for a different purpose and that his services were no longer required. In desperation, his father turned to the local Camorra boss, whose word was law in the village. The boss invited the Cutolo family to his home and promised to settle everything. A short time later, the landowner changed his mind and the contract was renewed.
A bad student, violent and inattentive, at 12 Cutolo was already roaming the streets with a gang of teenagers, committing petty burglaries and harassing shopkeepers. As soon as he could drive he bought a car, both for prestige and because it allowed him greater mobility in his raids. At the age of 21, on February 24, 1963, he committed his first homicide. He killed a man whose girlfriend had been slapped by Cutolo due to an alleged insult. In the ensuing fight, Cutolo pulled out a gun and shot him to death. He was convicted and sentenced to life imprisonment, reduced to 24 years after appeal. He was sent to Poggioreale prison in Naples. Entering the prison world on a murder conviction made Cutolo a “tough guy”. In prison Cutolo learned the rules of the criminal world: he became a man of honour, paid respect to more powerful inmates, and started gathering personal prestige because of his striking personality. He never lost sight of his ambition and his desire to become one of the biggest bosses of the Neapolitan underworld.
Cutolo had established himself as a ringleader, when Antonio Spavone, known as "'o Malommo" (The Badman), was transferred to Poggioreale prison. He challenged Spavone to a knife fight in the courtyard (a practice called 'o dichiaramento, the declaration), but Spavone refused. The challenged boss allegedly limited himself to a reply: "Today's young men want to die young by whatever means." Spavone was released from prison shortly after this event. From his prison cell, Cutolo ordered the murder of Spavone. A hitman, allegedly Cutolo's friend, shot Spavone in the face from short range with a shotgun. Spavone survived the ambush, but the shotgun blast left considerable damage to his facial structure, which required plastic surgery. Spavone immediately resigned from his highly visible role as a Camorra boss.
Cutolo was soon able to gather under him a small group of prisoners, the nucleus of which would later become the leadership of the NCO. They were Antonino Cuomo known as "'o Maranghiello" (The Cudgel), Pasquale Barra known as "'o Nimale" (The Animal), Giuseppe Puca known as "'o Giappone" (Japanese), Pasquale D'Amico known as "'o Cartunaro" (The Cardboard picker) and Vincenzo Casillo known as "'o Nirone" (The Big Black). After being released, they would set up criminal activities on the outside which would be directly controlled by Cutolo from within the penitentiary system.
From within Naples' Poggioreale prison Cutolo built a new organisation: the Nuova Camorra Organizzata (NCO). He began by befriending young inmates unfamiliar with jail, giving them a sense of identity and worth, so much so that when they were released they would send Cutolo ‘flowers’ (i.e. money), which enabled him to increase his network. He helped poorer prisoners by buying food for them from the jail store, or arranging for food to be sent in from outside. In such ways Cutolo created many ‘debts’ or ‘rain cheques’ which he would cash at the opportune moment. As his following grew, he also began to exercise a monopoly of violence within a number of prisons, thus increasing his power. By the early seventies, Cutolo had become so powerful that he was able to decide which of his followers would be moved to which jails, use a prison governor's telephone to make calls anywhere in the world, and allegedly even slap the prison governor on one occasion for daring to search his cell. Another key bond Cutolo created was regular payments to the families of NCO members sent to prison, thereby guaranteeing the allegiance of both prisoners and their families.