The application of complex networks to study complex phenomena, including the Internet, social networks, food networks, and others, has seen a growing interest in recent years. In particular, the use of complex networks and network theory to analyze the behavior of the climate system is an emerging topic. This newfound interest is due to the difficulty of analyzing climate data-this analysis is notoriously difficult due to the strong spatio-temporal dependencies, multivariate nature, seasonal behavior, and nonlinear phenomena inherent in the climate system. Network-based approaches model the complex long-term dependencies of weather attributes (such as temperature or air pressure) between locations on the Earth as a network of relationships and analyze these networks to gather insights about the emergent behavior of the system as a whole. In this paper, we describe our work-in-progress on a methodology for capturing and characterizing the evolution of the climate network. We do this by splitting the climate data into a set of overlapping decadal time windows and forming a network for each of these datasets representing the complex interdependencies in the climate system over the particular decade. We can then use this sequence of networks to characterize major patterns and anomalies in the data. We validate our methodology by identifying nontrivial events and trends in the evolution of the decadal networks and correlating these with known climatological phenomena.