Anecdotal reports of tsunamis climbing up coastlines have often described the shoreline receding significantly before the tsunami waves run-up on the beach. These waves are caused by tsunamigenic earthquakes close to the shoreline, when the generated wave does not have sufficient propagation distance to evolve into leading-elevation waves or a series of solitary waves. Yet all previous run-up investigations have modelled periodic waves or solitary waves which initially only run-up on the beach. In our studies of these initially receding shorelines, we have found a class of N-shaped waves with very interesting and counterintuitive behaviour which may lead to a new paradigm for the studies of tsunami run-up. We will use a first-order theory and we will derive asymptotic results for the maximum run-up within the validity of the theory for different types of N-waves. We have observed that leading depression N-waves run-up higher than leading elevation N-waves, suggesting that perhaps the solitary wave model may not be adequate for predicting an upper limit for the run-up of near-shore generated tsunamis.