Extreme sea level estimates are fundamental for mitigating against coastal flooding as they provide insight for defence engineering. As the global climate changes, rising sea levels combined with increases in storm intensity and frequency pose an increasing risk to coastline communities. We present a new method for estimating extreme sea levels that accounts for the effects of climate change on extreme events that are not accounted for by mean sea level trends. We follow a joint probabilities methodology, considering skew surge and peak tides as the only components of sea levels. We model extreme skew surges using a non-stationary generalised Pareto distribution (GPD) with covariates accounting for climate change, seasonality and skew surge-peak tide interaction. We develop methods to efficiently test for extreme skew surge trends across different coastlines and seasons. We illustrate our methods using data from four UK tide gauges and estimate sea level return levels when accounting for these longer term trends.