Recent advancements in ICT have sped up the development of new services in healthcare. In this context, remote patient monitoring and rehabilitation activities can take place either in satellite hospital centers or directly in patients’ homes. Specifically, using a combination of Cloud/Edge computing, Internet of Things (IoT) and Machine Learning (ML) technologies, patients with motor disabilities can be remotely assisted avoiding stressful waiting times and overcoming geographical barriers. This is possible by applying the Tele-Rehabilitation as a Service (TRaaS) concept. The objective of this paper is twofold: i) studying how Machine Learning can improve the TRaaS, and ii) demonstrating how a NoSQL graph database approach can enhance the performance because it works directly at the database layer instead of at application one. In particular, the K-Nearest Neighbors (K-NN) algorithm is studied in order to identify the best therapy, i.e., rehabilitation training, for a new remote patient with motor impairment. Experiments compare two system prototypes, that are respectively based on Python and Neo4j, showing that the latter presents better performance in terms of processing time guaranteeing the same accuracy.