Interfacing the smart cities with cyber-physical systems (CPSs) improves cyber infrastructures while introducing security vulnerabilities that may lead to severe problems such as system failure, privacy violation, and/or issues related to data integrity if security and privacy are not addressed properly. In order for the CPSs of smart cities to be designed with proactive intelligence against such vulnerabilities, anomaly detection approaches need to be employed. This chapter will provide a brief overview of the security vulnerabilities in CPSs of smart cities. Following a thorough discussion on the applicability of conventional anomaly detection schemes in CPSs of smart cities, possible adoption of distributed anomaly detection systems by CPSs of smart cities will be discussed along with a comprehensive survey of the state of the art. The chapter will discuss challenges in tailoring appropriate anomaly detection schemes for CPSs of smart cities and provide insights into future directions for the researchers working in this field.