Comparing time series of unequal length requires data processing procedures that may introduce biases. This article describes, validates, and applies Cross-Recurrence Quantification Analysis (CRQA) to detect and quantify correlation and coupling among time series of unequal length without prior data processing. We illustrate and validate this application using continuous and discrete data from a model system (study 1). Then we use the method to re-analyze the Sleep Heart Health Study (SHHS), a rare large dataset comprising detailed physiological sleep measurements acquired by in-home polysomnography. We investigate whether recurrence patterns of ultradian NREM/REM sleep cycles (USC) predict mortality (study 2). CRQA exhibits better performance compared with traditional approaches that require trimming, stretching or compression to bring two time series to the same length. Application to the SHHS indicates that recurrence patterns linked to stability of USCs are associated with all-cause mortality even after controlling for other sleep parameters, health, and sociodemographics. We suggest that CRQA is a useful tool for analyzing categorical time series, where the underlying structure of the data is unlikely to result in matching data points—such as ultradian sleep cycles.