A search for the production of heavy partners of the top quark with charge 5/3 (X5/3) decaying into a top quark and a W boson is performed with a data sample corresponding to an integrated luminosity of 2.3 fb−1, collected in proton-proton collisions at a center-of-mass energy of 13 TeV with the CMS detector at the CERN LHC. Final states with either a pair of same-sign leptons or a single lepton, along with jets, are considered. No significant excess is observed in the data above the expected standard model background contribution and an X5/3 quark with right-handed (left-handed) couplings is excluded at 95% confidence level for masses below 1020 (990) GeV. These are the first limits based on a combination of the same-sign dilepton and the single-lepton final states, as well as the most stringent limits on the X5/3 mass to date.