The increasing trend of outsourcing services to cloud providers is changing the way computing power is delivered to enterprises and end users. Although cloud services offer several advantages, they also make cloud consumers strongly dependent on providers. Hence, consumers have a vital interest to be immediately informed about any problems in their services. This paper aims at a first step toward a network-based approach to monitor cloud services. We focus on severe problems that affect most services, such as outages or extreme server overload, and propose a method to monitor these problems that relies solely on the traffic exchanged between users and cloud providers. Our proposal is entirely based on NetFlow/IPFIX data and, therefore, explicitly targets high-speed networks. By combining a methodology to reassemble and classify flow records with stochastic estimations, our proposal has the distinct characteristic of being applicable to both sampled and non-sampled data. We validate our proposal and show its applicability using data collected at both the University of Twente and an international backbone during the WikiLeaks Cablegate. Our results show that, in contrast to Anonymous’ claims, the users of the targeted services have been only marginally affected by the attacks.