A search for heavy resonances that decay to tau lepton pairs is performed using proton-proton collisions at s=13 TeV. The data were collected with the CMS detector at the CERN LHC and correspond to an integrated luminosity of 2.2 fb−1. The observations are in agreement with standard model predictions. An upper limit at 95% confidence level on the product of the production cross section and branching fraction into tau lepton pairs is calculated as a function of the resonance mass. For the sequential standard model, the presence of Z′ bosons decaying into tau lepton pairs is excluded for Z′ masses below 2.1 TeV, extending previous limits for this final state. For the topcolor-assisted technicolor model, which predicts Z′ bosons that preferentially couple to third-generation fermions, Z′ masses below 1.7 TeV are excluded, representing the most stringent limit to date.[Figure not available: see fulltext.]