The first measurement of the CP structure of the Yukawa coupling between the Higgs boson and $\tau$ leptons is presented. The measurement is based on data collected in proton-proton collisions at $\sqrt{s} =$ 13 TeV by the CMS detector at the LHC, corresponding to an integrated luminosity of 137 fb$^{-1}$. The analysis uses the angular correlation between the decay planes of $\tau$ leptons produced in Higgs boson decays. The effective mixing angle between CP-even and CP-odd $\tau$ Yukawa couplings is found to be $-$1 $\pm$ 19$^\circ$, compared to an expected value of 0 $\pm$ 21$^\circ$ at the 68.3% confidence level. The data disfavour the pure CP-odd scenario at 3.0 standard deviations. The results are compatible with predictions for the standard model Higgs boson.