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. The second model considers pair production of leptoquarks with decays into third-generation leptons and quarks. Depending on the branching fraction into charged leptons, leptoquarks with masses up to around 1.25 TeV can be excluded at the 95% confidence level for the case of scalar leptoquarks and up to 1.8 TeV (1.5 TeV) for vector leptoquarks in a Yang-Mills (minimal-coupling) scenario. In addition, model-independent upper limits are set on the cross section of processes beyond the Standard Model.