Ultrarelativistic heavy ion collisions recreate in the laboratory the thermodynamical conditions prevailing in the early universe up to 10-6 sec, thereby allowing the study of the quark-gluon plasma (QGP), a state of quantum chromodynamics (QCD) matter with deconfined partons. The top quark, the heaviest elementary particle known, is accessible in nucleus-nucleus collisions at the CERN LHC, and constitutes a novel probe of the QGP. Here, we report the first evidence for the production of top quarks in nucleus-nucleus collisions, using lead-lead collision data at a nucleon-nucleon center-of-mass energy of 5.02 TeV recorded by the CMS experiment. Two methods are used to measure the cross section for top quark pair production (σtt) via the selection of charged leptons (electrons or muons) and bottom quarks. One method relies on the leptonic information alone, and the second one exploits, in addition, the presence of bottom quarks. The measured cross sections, σtt=2.54-0.74+0.84 and 2.03-0.64+0.71 μb, respectively, are compatible with expectations from scaled proton-proton data and QCD predictions.