Anatol Heintz er internasjonalt kjent for sin forskning på fossile fisker fra Svalbard og fastlands-Norge. Som konservator og professor ved Paleontologisk museum og ikke minst som forfatter av lære- og faktabøker var han en dyktig formidler.
Heintz vokste opp i St. Petersburg som den yngste av tre søsken. Han avsluttet gymnaset 1915 og begynte samme år på forstakademiet. Januar 1919 flyktet han, hans mor og søster fra revolusjonens og borgerkrigens Russland til Norge. Det første året i Norge gikk han på Statens Håndverks- og Kunstindustriskole. Fra 1920 studerte han ved universitetet i Kristiania, og han avla embetseksamen med paleontologi som hovedfag 1928. Hans lærer, professor Johan Kiær, introduserte ham til studier av fossile urfisker og fisk fra devonperioden. Fra 1922 var han tilknyttet Paleontologisk museum på Tøyen, og 1928 ble han ansatt som konservator. Han disputerte for doktorgraden høsten 1932. April 1940 ble han utnevnt til professor i paleontologi og bestyrer av Paleontologisk museum, og han innehadde disse stillingene til han gikk av 1966.
Allerede 1925 var Heintz med på en ekspedisjon til Svalbard. Mye av det materialet som ble innsamlet på denne og Heintz' øvrige seks ekspedisjoner til Svalbard, dannet grunnlaget for en stor del av hans vitenskapelige produksjon, og han videreførte også Kiærs vitenskapelige arbeider over urfisk fra Svalbard. 1939 publiserte Heintz beskrivelsen av cephalaspider (urfisk) fra silur som var funnet på Ringerike omkring 1910. Han beskrev også de fleste funn av mammut i Norge. Noe ble karbon-14-datert, og dette bidrog til en bedre forståelse av mammutens tidsutbredelse i Norge under siste istid.
Fra 1930-årene stod Heintz for undervisningen i paleontologi ved Universitetet i Oslo. Han holdt innledningskursene i paleontologi og historisk geologi, og han veiledet hovedfagsstudenter. Sammen med Leif Størmer utarbeidet han en stor plansje over dyrelivets utvikling, som senere ble benyttet i mange norske og utenlandske lærebøker.
1941 utgav Heintz den populærvitenskapelige boken Menneskets avstamning, og han ajourførte og moderniserte Kiærs bok Verdner som svant. Fra urfisk til ape. 1966 utgav han sammen med datteren Natascha Heintz en helt ny utgave av Menneskets avstamning. Sammen med Henrik Aasekjær utgav han 1940 en lærebok i zoologi for realskolen, hvor han selv også tegnet alle illustrasjonene. Den siste ajourførte utgaven kom 1971 og omfattet da både zoologi og botanikk for ungdomsskolen.
Heintz var tidlig meget interessert i museets samlinger og utformingen av utstillingene. Han var opptatt av å gjøre utstillingene både estetisk vakre og med et klart, faglig innhold. Gjennom hele sin yrkesaktive tid besøkte Heintz mange museer i Europa og USA, og han fikk mange impulser til forbedring av utstillingene. 1938 tok han initiativet til stiftelsen av Norske naturhistoriske museers landsforbund (NNML) og var forbundets første formann til 1949 og igjen 1958–61.
Heintz ble arrestert av den tyske okkupasjonsmakten oktober 1943 og kom desember samme år til Grini, hvor han ble til 24. desember 1944. I løpet av tiden på Grini holdt han utallige populærvitenskapelige foredrag, særlig om livets utvikling på jorden. Han deltok i en rekke offentlige avisdebatter, bl.a. 1947 om forholdet mellom kristendom og utviklingslære i skolens pensum. 1955 skrev han artikkelen Kulturens morgen. Fra urmenneske til kulturmenneske i første bind av Grimbergs Menneskets liv og historie. Dette førte til en meget omfattende avisdebatt, hvor særlig antroposofene gikk kraftig til angrep på Heintz' fremstilling.
Anatol Heintz var formann i Norsk Geologisk Forening 1945–46, medlem av Det Norske Videnskaps-Akademi, hvor han var formann i Matematisk-naturvitenskapelig klasse 1954–58, og æresmedlem i Geological Society of London. Han fikk Kongens gullmedalje 1939, Reuschmedaljen 1935 og Framkomiteens Nansenbelønning 1967.