A search for dark matter produced in association with a Higgs boson in final states with two hadronically decaying tau-leptons and missing transverse momentum is presented. The analysis uses 139 fb(-1) of proton-proton collision data at root s = 13 TeV collected by the ATLAS experiment at the Large Hadron Collider between 2015 and 2018. No evidence of physics beyond the Standard Model is found. The results are interpreted in terms of a 2HDM+a model featuring two scalar Higgs doublets and a pseudoscalar singlet field. Exclusion limits on the parameters of the model in selected benchmark scenarios are derived at 95% confidence level. Model-independent limits are also set on the visible cross-section for processes beyond the Standard Model producing missing transverse momentum in association with a Higgs boson decaying into tau-leptons.