Gravano received his first murder assignment in early 1970. Joseph Colucci was a member of Shorty Spero's crew. Gravano had heard the mob gossip that Tommy Spero was having an affair with Colucci's attractive wife, but thought nothing of it. The way Gravano explained the turn of events was that he was told Colucci was gunning for him. The reason for this, as explained to Gravano, was that after Colucci killed both him and Shorty he could then seek revenge on Tommy without having to worry about retaliation. Colucci's mistake in this twisted plot was taking into confidence another member of the crew who quickly ratted him out.

Using the man Colucci had confided in, Gravano and Tommy Spero planned the murder. After a night of drinking and dancing at the local clubs, Colucci was lulled into a false sense of security. After leaving a diner around 4:00 a.m., the four men piled into an automobile. While a Beatles' tune filled the air, Gravano performed his first hit for the mob. In Underboss he describes the murder:

"As that Beatles song played, I became a killer. Joe Colucci was going to die. I was going to kill him because he was plotting to kill me. I felt the rage inside me. You fucking cocksucker, I thought. Even if I wasn't directly behind him, I felt invisible. I pointed the gun at the back of his head. Everything went in slow motion. I could almost feel the bullet leaving the gun and entering his skull. It was strange. I didn't hear the first shot. I didn't see any blood. His head didn't seem to move, like it was a blank instead of a real bullet. I knew I couldn't have missed, the gun was only inches from his head, but I felt like I was a million miles away, like this was all a dream.

"I shot a second time in the same spot. This time everything was different. I saw the flash. I smelt the gunpowder. The noise was deafening. Now I saw his head jerk back, his body convulse and slip sideways. I saw the blood. Joe Colucci was dead. He looked like he was sleeping. He looked peaceful. You going to blow me away now? I thought."

Although the other occupants were in on the plot, bedlam seemed to fill the car. Driving to a secluded area to dump the body, Tommy Spero, who was behind the wheel, told Gravano he was unable to touch the body of his old friend. Gravano climbed out of the back seat, pulled Colucci's body out of the car, and left it face down in the street. He got back in the car, rolled down the window and fired three more shots into the body.

Again in Underboss, Gravano reveals his thoughts about the murder:

"We were all scared, not like afraid, but excited. But then I felt a surge of power. I realized that I had taken a human life, that I had the power over life and death. I was a predator. I was an animal. I was Cosa Nostra.

"That afternoon I was hanging out on a street corner, listening as everybody around was talking about Joe Colucci being hit and who would want to kill him? I felt like I was in space as I listened. Like I wasn't there. I was thinking, Am I supposed to feel remorse? If anything, I felt good. Like high. Like powerful, maybe even superhuman. It's not that I was happy or proud of myself. Not that. I'm still not happy about that feeling. It's just that killing came so easy to me."

Carmine Persico

A short time after the killing, Gravano and Tommy Spero were called to a hotel room in midtown Manhattan. Here Tommy described the murder to the hierarchy of the Colombo Family Carmine "Junior" Persico, Gennaro "Gerry Lang" Langella, Salvatore Albanese, "Alley Boy" Persico, Hugh "Apples" McIntosh and Shorty Spero. Afterwards Shorty told Gravano that Persico said they had done a good job.

"Junior loves you," Spero told him. "He's real proud of you."

Sometime after the trio of killers grieved at Colucci's funeral, Tommy Spero married the widow. Gravano reveals with a bitter tone, "It didn't last long. She saw him for what he was, a total nothing, and left him for another guy. (Later) he was whining at some meeting and I heard Gerry Lang slapped him in the face. That's the worst insult you could have. He didn't have no standing after that. They told me he ended up half a junkie."