We face a new era in the assessment of multiple natural hazards whose statistics are becoming alarmingly non-stationary due to ubiquitous long-term changes in climate. One particular case is tsunami hazard affected by climate-change-driven sea level rise (SLR). A traditional tsunami hazard assessment approach where SLR is omitted or included as a constant sea-level offset in a probabilistic calculation may misrepresent the impacts of climate-change. In this paper, a general method called non-stationary probabilistic tsunami hazard assessment (nPTHA), is developed to include the long-term time-varying changes in mean sea level. The nPTHA is based on a non-stationary Poisson process model, which takes advantage of the independence of arrivals within non-overlapping time-intervals to specify a temporally varying hazard mean recurrence rate, affected by SLR. The nPTHA is applied to the South China Sea (SCS) for tsunamis generated by earthquakes in the Manila Subduction Zone. The method provides unique and comprehensive results for inundation hazard, combining tsunami and SLR at a specific location over a given exposure time. The results show that in the SCS, SLR has a significant impact when its amplitude is comparable to that of tsunamis with moderate probability of exceedance. The SLR and its associated uncertainty produce an impact on nPTHA results comparable to that caused by the uncertainty in the earthquake recurrence model. These findings are site-specific and must be analyzed for different regions. The proposed methodology, however, is sufficiently general to include other non-stationary phenomena and can be exploited for other hazards affected by SLR.