Heller wrote: "There was only one catch and that was Catch 22, which specified that a concern for one's safety in the face of dangers that were real and immediate was the process of a rational mind.
Heller, who was 76, died on Sunday night, according to his wife, Valerie.
On hearing the news, author Kurt Vonnegut said: "This is a calamity for American letters."
The writer and academic, Professor Malcolm Bradbury, said Heller had been "one of the great post-war American writers."
The author JG Ballard said Heller had "changed attitudes towards war."
Heller based the novel on his own experiences of the Army Air Corps during World War II. He was a bombardier in combat over Italy and flew 60 missions before he was discharged as a lieutenant at the end of the war.
He wrote five novels after Catch 22 and co-authored the non-fiction No Laughing Matter, which told of his bout of Guillain-Barre syndrome in the early 1980s - a paralysing nerve disorder from which he never fully recovered.
Only one catch
All his works were inevitably compared to Catch 22 - a darkly comic account of the exploits of Captain John Yossarian and the rest of his squadron.
The only hope the fighters had to avoid combat was to plead insanity - but to do so would prove that they understood the missions were dangerous, and therefore they were sane.
Heller wrote: "There was only one catch and that was Catch 22, which specified that a concern for one's safety in the face of dangers that were real and immediate was the process of a rational mind.
"Orr (a character in the novel) was crazy and could be grounded. All he had to do was ask, and as soon as he did, he would no longer be crazy and would have to fly more missions.
"Orr would be crazy to fly more missions and sane if he didn't, but if he was sane he had to fly them. If he flew them he was crazy and didn't have to; but if he didn't want to he was sane and had to."
The novel became one of the most extravagantly praised works of fiction of the 1960s, and introduced the Catch 22 no-win dilemma into the English language.
Curmudgeon no more
Arthur Gelb, former managing editor of The New York Times and a longtime friend of the author, told the Associated Press of a dinner party the pair attended last month.
"He had this never-flagging satirical wit that was always entertaining - except when you were in the path of one of his ascerbic bullets.
"But that evening, he was sweet-tempered and somewhat subdued. I asked him if he was feeling well," Mr Gelb said.
"He said he regretted to report that age appeared to be mellowing him, and that people would have to stop referring to him as a curmudgeon."
Vietnam
Professor Malcolm Bradbury said: "Catch-22 is one of those books that really caught the mood...The war it is about, though apparently the Second World War, is Vietnam - that was why it was successful.
"The prevailing sense of the futility of war and everything to do with war, killing and being killed, that runs through the book wouldn't have gone down very well in 1945 or 1946 but by the beginning of the 60s it really worked."