He was born in Petrograd to the geophysicist Yevgeniy Alfredovich Heintz (1869–1918) and Olga Fyodorovna Hoffmann (1871–1958). He had two older siblings. In 1919 the family fled to Norway. He studied at the Norwegian National Academy of Craft and Art Industry from 1919 to 1920 and at the Royal Frederick University from 1920, where he graduated in palaeontology in 1928. He was then hired as a curator at the Paleontological Museum of Tøyen. He took the dr.philos. degree in 1932 on the thesis The Structure of Dinichtys. A Contribution to our Knowledge of the Arthrodira. As a researcher he was inspired by Johan Kiær, and specialized in ancient fish, conducting paleontological expeditions to Svalbard. In 1939 he published Cephalaspida from Downtonian of Norway, about cephalaspida excavated at Ringerike. He was appointed professor at the University of Oslo and director of the Paleontological Museum in 1940.
In 1940 Norway was occupied by Nazi Germany. Open protests ensued when the Nazi authorities were about to change the rules for admission to the university in autumn 1943. In retaliation, the Gestapo arrested 11 staff, 60 male students and 10 female students. The staff Johannes Andenæs, Bjørn Føyn, Johan Christian Schreiner, Eiliv Skard, Harald K. Schjelderup, Odd Hassel, Ragnar Frisch, Carl Jacob Arnholm, Endre Berner and Anatol Heintz were sent to Grini concentration camp. Heintz was incarcerated at Bredtveit from 15 October to 22 November, then at Berg until 8 December, then at Grini until 24 December 1944. While at Grini he held numerous popular science lectures for the other inmates.
After the war he assumed his positions as professor and director, which he held until retiring in 1966. He was also chairman of Norsk Geologisk Forening from 1945 to 1946, and co-founder and first chairman of Norske naturhistoriske museers landsforbund from 1938 to 1949 and 1958 to 1961. He was also a fellow of the Norwegian Academy of Science and Letters and an honorary member of the Geological Society of London.
- Nakrem, Hans Arne. "Anatol Heintz". In Helle, Knut. Norsk biografisk leksikon (in Norwegian). Oslo: Kunnskapsforlaget. Retrieved 14 January 2010.
- Nøkleby, Berit (1995). "Universitetet". In Dahl; Hjeltnes; Nøkleby; Ringdal; Sørensen. Norsk krigsleksikon 1940-45 (in Norwegian). Oslo: Cappelen. Retrieved 3 January 2010.
- Giertsen, Børre R., ed. (1946). Norsk fangeleksikon. Grinifangene (in Norwegian). Oslo: Cappelen. p. 330.
- Nakrem, Hans Arne. "Natascha Heintz". In Helle, Knut. Norsk biografisk leksikon (in Norwegian). Oslo: Kunnskapsforlaget. Retrieved 14 January 2010.