The turmoil in the sovereign debt markets in Europe has raised concerns on the usefulness of sovereign credit default swaps and government bond yields in periods of distress. In addressing this issue, we introduce a novel nonlinear approach for the analysis of non-stationary multivariate data based on complex networks and recurrence analysis. We show the relevance of the approach in studying joint risk connections, extracting hidden spatial information, time dependence, detection of regime changes and providing early warning indicators. The feasibility and relevance of the approach in studying systemic risk is discussed. Finally, we share more light on possible extensions and applications of the approach to systemic risk.