Internet of Medical Things (IoMT) is a significant aspect of today’s digital world that provides a range of health services for the users. However, as IoMT deals with wide range of health related crucial data, ensuring security and privacy of these data is a vital aspect. From a rigorous literature review we found that all the existing protocols/schemes are either prone to various security threats or incurs high computation/communication overheads. Therefore, in order to mitigate these security threats we have designed a novel Mutual Authentication and Key Establishment scheme for IoMT (MAKE-IoMT) environment which emphasizes to establish mutual authentication among all the involved IoMT entities. We have performed informal security validation of our scheme and the result shows that the MAKE-IoMT scheme resists all the well-known security threats. Further, the formal security verification of our scheme is performed using widely-known AVISPA tool and the simulation result shows that the MAKE-IoMT is SAFE against security attacks. Moreover, the performance evaluation with respect to computation and communication overheads of our scheme is carried out and compared with other existing schemes that show that the MAKE-IoMT scheme maintains the trade-off between security and efficiencies, and is implementable in a real-world IoMT environment.