“Complex network analysis” constitutes a powerful tool to investigate local and non-local statistical interrelationships. It refers to a set of metrics, modeling tools and algorithms commonly used in the study of complex nonlinear dynamical systems and its main premise is that the underlying topology or network structure of a system has a strong impact on its dynamics and evolution. Here we present a fast, scalable and cutting-edge computational toolbox to infer networks for climate systems and we analyze the network structure, and therefore the teleconnections, of both observational data-sets and CMIP5 climate model outputs. With an extensive model intercomparison in terms of the climate network that each model leads to, we quantify how each model reproduces major teleconnections and identify common or specific errors in comparing model outputs and observations. We therefore discuss sources of uncertainties in climate models, clustering models or integrations with qualitatively different topological characteristics as distinct climate scenarios.