A search is performed for a heavy Majorana neutrino (N), produced in leptonic decay of a W boson propagator and decaying into a W boson and a lepton, with the CMS detector at the LHC. The signature used in this search consists of two same-sign leptons, in any flavor combination of electrons and muons, and at least one jet. The data were collected during 2016 in proton-proton collisions at a center-of-mass energy of 13 TeV, corresponding to an integrated luminosity of 35.9 fb−1. The results are found to be consistent with the expected standard model background. Upper limits are set in the mass range between 20 and 1600 GeV in the context of a Type-I seesaw mechanism, on |VeN|2, |VμN|2, and |VeNV μN * |2/(|VeN|2 + |VμN|2), where VℓN is the matrix element describing the mixing of N with the standard model neutrino of flavor ℓ = e, μ. For N masses between 20 and 1600 GeV, the upper limits on |VℓN|2 range between 2.3 × 10−5 and unity. These are the most restrictive direct limits for heavy Majorana neutrino masses above 430 GeV.