While online medical diagnosis provides significant convenience to users, it also incurs the risk of privacy breaches, which inspired the emergence of various privacy-preserving online medical schemes. Nonetheless, existing schemes either compromise partial privacy to third parties or rely on cryptographic methods with high computational complexity. In particular, they do not anticipate user’s disputes to the extent that there is no audit process to guarantee the correctness of the diagnosis results and the fairness of the schemes. Consequently, we propose an efficient and privacy-preserving online medical diagnosis scheme based on additive secret sharing (ASS). First, the anonymity of the user is provided in the medical diagnosis process, which ensures that the cloud cannot link the diagnosis results to the user. Then, we devise a minimum value protocol and a range comparison protocol to enhance the security of the online diagnosis. In addition, considering user’s disputes that arise in realistic scenarios (e.g., malicious users may cheat the diagnosis system for personal benefits), we construct a blockchain-based audit process to detect user’s behaviors and settle controversies. Finally, we demonstrate the security and efficiency of the proposed scheme with theoretical analysis and experimental evaluation.