Appel, who was born in Brooklyn, New York City, was educated at the University of Michigan, where he completed his PhD in 1959. After working for two years at the Institute for Defense Analysis at Princeton, he joined the faculty of the University of Illinois, Urbana, where he served as professor of mathematics from 1991 to 1993. He then took up the chairmanship of the mathematics department at the University of New Hampshire.

In 1976, in collaboration with Wolfgang Haken (1928– ), Appel announced the solution to one of mathematics long-standing unsolved problems, the four-color map problem. In 1852 Francis Guthrie had noticed that it seemed to be possible to color any map, assuming countries with common borders were colored differently, with no more than four colors. Guthrie was sufficiently intrigued by the point to raise it with the mathematician de Morgan and ask for a proof of the conjecture. De Morgan found the problem unexpectedly difficult, as did succeeding generations of mathematicians.

Appel and Hagen used a variation of a method first tried by Arthur Kempe in 1879. It depends on the fact that maps must contain certain unavoidable configurations – Appel and Hagen recognized 1482 of these. They then used a computer to show that all of these could be reduced to four-color configurations. They began work in 1972, but it was not until 1976 that they were satisfied with their analysis and their program. It took more than 1200 hours of computer time to prove the theorem.