A search is performed for a pseudoscalar Higgs boson, A, decaying into a 125 GeV Higgs boson h and a Z boson. The h boson is specifically targeted in its decay into a pair of tau leptons, while the Z boson decays into a pair of electrons or muons. A data sample of proton-proton collisions collected by the CMS experiment at the LHC at $\sqrt{s} =$ 13 TeV is used, corresponding to an integrated luminosity of 35.9 fb$^{-1}$. No excess above the standard model background expectations is observed in data. A model-independent upper limit is set on the product of the gluon fusion production cross section for the A boson and the branching fraction to Zh$\to\ell\ell\tau\tau$. The observed upper limit at 95% confidence level ranges from 27 to 5 fb for A boson masses from 220 to 400 GeV, respectively. The results are used to constrain the extended Higgs sector parameters for two benchmark scenarios of the minimal supersymmetric standard model.