A search for charged Higgs bosons heavier than the top quark and decaying via H± → tb is presented. The data analysed corresponds to 36.1 fb−1 of pp collisions at s=13 TeV and was recorded with the ATLAS detector at the LHC in 2015 and 2016. The production of a charged Higgs boson in association with a top quark and a bottom quark, pp → tbH±, is explored in the mass range from mH± = 200 to 2000 GeV using multi-jet final states with one or two electrons or muons. Events are categorised according to the multiplicity of jets and how likely these are to have originated from hadronisation of a bottom quark. Multivariate techniques are used to discriminate between signal and background events. No significant excess above the background-only hypothesis is observed and exclusion limits are derived for the production cross-section times branching ratio of a charged Higgs boson as a function of its mass, which range from 2.9 pb at mH± = 200 GeV to 0.070 pb at mH± = 2000 GeV. The results are interpreted in two benchmark scenarios of the Minimal Supersymmetric Standard Model.[Figure not available: see fulltext.].