Prosecutors say Peter Gotti sent hitmen armed with a bomb to Arizona to find Gravano, who was living in Phoenix under an assumed name after his testimony sent John Gotti to jail for life. The don died last year.
The plot was abandoned after Gravano, who served only five years in prison for 19 murders after cooperating with police, was arrested for running an ecstasy ring.
In an interview with Vanity Fair, Gravano said he knew the crime family would come to get him.
He left the witness protection programme in 1999 and was bullish about his response if they found him.
"They send a hit team down, I'll kill them," he said. "They better not miss, because even if they get me, there will be a lot of body bags going back to New York."
Peter Gotti was convicted in March of racketeering and other offences. That case accused him of taking control of the Gambino family after John Gotti's son was jailed.
He faces up to 70 years in prison on the new charges, which also include accusations that he tried to extort money from construction companies.