To facilitate successful adoption of algorithmic solutions for medical decision-making, we need to identify strategies for engaging patients, who are the beneficiaries of such solutions. In this paper, we investigate how the quantity and complexity of information related to the inner mechanics of algorithmic solutions for medical decision-making can impact patients’ perceived quality of healthcare. We propose an inverse U-shaped relationship between possessed information and perceived quality of healthcare of algorithmic solutions for medical decision-making. We develop a theoretical framework based on organizational information processing theory and protection motivation theory, that can inform the optimal level of information shared with patients to increase their perceived quality of healthcare, while considering patient-specific characteristics. Our findings contribute to the literature on human-algorithm interactions and the broader field of health information systems. We discuss the theoretical and practical implications of our work and delineate an agenda for future research on the topic.