A search for new phenomena in final states with hadronically decaying tau leptons, b-jets, and missing transverse momentum is presented. The analyzed dataset comprises pp collision data at a center-of-mass energy of s=13 TeV with an integrated luminosity of 139 fb-1, delivered by the Large Hadron Collider and recorded with the ATLAS detector from 2015 to 2018. The observed data are compatible with the expected Standard Model background. The results are interpreted in simplified models for two different scenarios. The first model is based on supersymmetry and considers pair production of top squarks, each of which decays into a b-quark, a neutrino and a tau slepton. Each tau slepton in turn decays into a tau lepton and a nearly massless gravitino. Within this model, top-squark masses up to 1.4 TeV can be excluded at the 95% confidence level over a wide range of tau-slepton masses.