The shift towards cloud-native applications has gained momentum in the past few years. Nevertheless, the inherent distributed architecture of these applications, in some cases across the edge and cloud continuum, represents unique security challenges. The more (micro-) components and network communications between them, the more complex detecting and mitigating security threats is. To tackle such issues, this paper presents a novel federated learning-based approach incorporating supervised machine learning approaches capable of performing traffic anomaly detection in such challenging environments, with a strong focus on three prominent challenges: which algorithm to use, which network features to consider and the data security and privacy. To evaluate the proposed approach, three supervised approaches commonly usedfor anomaly detection [26] were compared: Random Forest, SVMs and CNNs, in an isolated environment and then in a decentralised one, using four different performance metrics (i.e., accuracy, precision, recall and f1-score) and two types of attacks usually found in network environments: Denial of Service and Port Scan. In the validation scenario, the implemented approach with the best performance of f1-score presented 100.0% and 99.97%, respectively, for the Denial of Service and Port Scan attacks. The attained results allowed us to conclude the intrinsic value of the proposed approach for improving the security of emerging Cloud-Native applications and the value of the assessed algorithms for efficiently detecting network anomalies.