He was born into a German-Jewish family. He was a student at the universities of Berlin, Freiburg and Göttingen, where he met Edmund Landau, who supervised his doctorate. In his thesis, he improved a result of Hoheisel on the size of prime gaps.
Heilbronn fled Germany for Britain in 1933 due to the rise of Nazism. He arrived in Cambridge, then found accommodation in Manchester and eventually was offered a position at Bristol University, where he stayed for about one and a half years. There he proved that the class number of the number field tends to plus infinity as d does, as well as, in collaboration with Edward Linfoot, that there are at most ten quadratic number fields of the form , d a natural number, with class number 1. On invitation of Louis Mordell he moved back to Manchester in 1934, but left again only one year later, accepting the Bevan Fellowship at Trinity College, Cambridge. In Cambridge Heilbronn published several joint papers with Harold Davenport, in one of which they devised a new variant of the Hardy-Littlewood circle method, now sometimes referred to as the Davenport-Heilbronn method, proving that for any indefinite diagonal form f of degree k in more than n = 2k variables whose coefficients are not all in rational ratio there exists x in such that | f(x) | is arbitrarily small. During the Second World War he was briefly interned as an enemy alien but released to serve in the British Army. In 1946 he returned to Bristol, becoming Henry Overton Wills Professor of Mathematics. He was elected a Fellow of the Royal Society in 1951 and was president of the London Mathematical Society from 1959 to 1961.
Heilbronn and his wife moved to North America in 1964. He stayed at the California Institute of Technology for a while, then moved on to Toronto, where he was Professor of Mathematics at the University of Toronto from 1964 to 1975. He became a Canadian citizen in 1970.
His PhD students include Inder Chowla and Albrecht Fröhlich.