The analysis of palaeoclimate time series is usually affected by severe methodological problems, resulting primarily from non-equidistant sampling and uncertain age models. As an alternative to existing methods of time series analysis, in this paper we argue that the statistical properties of recurrence networks – a recently developed approach – are promising candidates for characterising the system's nonlinear dynamics and quantifying structural changes in its reconstructed phase space as time evolves. In a first order approximation, the results of recurrence network analysis are invariant to changes in the age model and are not directly affected by non-equidistant sampling of the data. Specifically, we investigate the behaviour of recurrence network measures for both paradigmatic model systems with non-stationary parameters and four marine records of long-term palaeoclimate variations. We show that the obtained results are qualitatively robust under changes of the relevant parameters of our method, including detrending, size of the running window used for analysis, and embedding delay. We demonstrate that recurrence network analysis is able to detect relevant regime shifts in synthetic data as well as in problematic geoscientific time series. This suggests its application as a general exploratory tool of time series analysis complementing existing methods.