The integration of the Internet of Things (IoT) and the telecare medical information system (TMIS) enables patients to receive timely and convenient healthcare services regardless of their location or time zone. Since the Internet serves as the key hub for connection and data sharing, its open nature presents security and privacy concerns and should be considered when integrating this technology into the current global healthcare system. Cybercriminals target the TMIS because it holds a lot of sensitive patient data, including medical records, personal information, and financial information. As a result, when developing a trustworthy TMIS, strict security procedures are required to deal with these concerns. Several researchers have proposed smart card-based mutual authentication methods to prevent such security attacks, indicating that this will be the preferred method for TMIS security with the IoT. In the existing literature, such methods are typically developed using computationally expensive procedures, such as bilinear pairing, elliptic curve operations, etc., which are unsuitable for biomedical devices with limited resources. Using the concept of hyperelliptic curve cryptography (HECC), we propose a new solution: a smart card-based two-factor mutual authentication scheme. In this new scheme, HECC’s finest properties, such as compact parameters and key sizes, are utilized to enhance the real-time performance of an IoT-based TMIS system. The results of a security analysis indicate that the newly contributed scheme is resistant to a wide variety of cryptographic attacks. A comparison of computation and communication costs demonstrates that the proposed scheme is more cost-effective than existing schemes.