Over the past few years, the healthcare sector is being transformed due to the rise of the Internet of Things (IoT) and the introduction of the Internet of Medical Things (IoMT) technology, whose purpose is the improvement of the patient’s quality of life. Nevertheless, the heterogenous and resource-constrained characteristics of IoMT networks make them vulnerable to a wide range of threats. Thus, novel security mechanisms, such as accurate and efficient anomaly-based intrusion detection systems (AIDSs), considering the inherent limitations of the IoMT networks, need to be developed before IoMT networks reach their full potential in the market. Towards this direction, in this paper, we propose an efficient and effective anomaly-based intrusion detection system (AIDS) for IoMT networks. The proposed AIDS aims to leverage host-based and network-based techniques to reliably collect log files from the IoMT devices and the gateway, as well as traffic from the IoMT edge network, while taking into consideration the computational cost. The proposed AIDS is to rely on machine learning (ML) techniques, considering the computation overhead, in order to detect abnormalities in the collected data and thus identify malicious incidents in the IoMT network. A set of six popular ML algorithms was tested and evaluated for anomaly detection in the proposed AIDS, and the evaluation results showed which of them are the most suitable.