Detection of anomalies in large Cloud infrastructure is challenging. Understanding operational behavior of Cloud is extremely difficult due to the heterogeneity of different technologies, virtualized platforms and complex interactions among the systems. Many of existing system models for Cloud are based on utilization metrics such as CPU, memory, network and I/O. Such system models are quite complex and their anomaly detection mechanisms are mostly based on threshold scheme. Utilization metrics exceeding a certain threshold would trigger an alarm. In fact, it is impossible to determine proper threshold for all anomalies. These system models fail to assess the state of the system accurately. We propose a novel anomaly detection system based on user perception rather than complex system models. In our Perception-Based Anomaly Detection system (PBAD), each component within multi-tier applications monitors response time and determines whether overall service response time is adequate. PBAD also locates the anomaly by analyzing component behaviors. PBAD masks the complexity of Cloud and addresses what matters, how user perceives the service provided by the Cloud applications. The key advantages of the proposed algorithm are simplicity and scalability. We implement and deploy PBAD in our production data center environment. The experimental results show that PBAD detects numerous types of anomalies as well as the combination of anomalies where existing systems fail.