A search for a heavy CP-odd Higgs boson, A, decaying into a Z boson and a heavy CP-even Higgs boson, H, is presented. It uses the full LHC Run 2 dataset of pp collisions at s = 13 TeV collected with the ATLAS detector, corresponding to an integrated luminosity of 140 fb−1. The search for A → ZH is performed in the ℓ+ℓ−tt¯ and νν¯bb¯ final states and surpasses the reach of previous searches in different final states in the region with mH > 350 GeV and mA > 800 GeV. No significant deviation from the Standard Model expectation is found. Upper limits are placed on the production cross-section times the decay branching ratios. Limits with less model dependence are also presented as functions of the reconstructed m(tt¯) and m(bb¯) distributions in the ℓ+ℓ−tt¯ and νν¯bb¯ channels, respectively. In addition, the results are interpreted in the context of two-Higgs-doublet models.