Despite the benefits of the passive keyless entry and start (PKES) system in improving the locking and starting capabilities, it is vulnerable to relay attacks even though the communication is protected using strong cryptographic techniques. In this paper, we propose a data-intensive solution based on machine learning to mitigate relay attacks on PKES Systems. The main contribution of the paper, beyond the novelty of the solution in using machine learning, is in (1) the use of a set of security features that accurately profiles the PKES system, (2) identifying abnormalities in PKES regular behavior, and (3) proposing a countermeasure that guarantees a desired probability of detection with a fixed false alarm rate by trading off the training time and accuracy. We evaluated our method using the last three months log of a PKES system using the Decision Tree, SVM, KNN and ANN and provide the comparative analysis of the relay attack detection results. Our proposed framework leverages the accuracy of supervised learning on known classes with the adaptability of k-fold cross-validation technique for identifying malicious and suspicious activities. Our test results confirm the effectiveness of the proposed solution in distinguishing relayed messages from legitimate transactions.