The Internet of Medical Things (IoMTs) is widely used today, and its efficiency and convenience benefit areas with poor medical conditions. At the same time, some incorrect diagnoses may also aggravate patients’ conditions, so traceability is needed. This paper focuses on an efficient and traceable threshold signature scheme. Our scheme can trace all signers, and the tracing is only carried out in the case of misdiagnosis resulting in patient loss, which greatly protects the privacy of both doctors and patients. Besides, compared with the other three schemes, our signature scheme has the advantage of faster signature verification after the multi-signer signature and the minimal communication cost.