Background Whilst the use of artificial intelligence (AI) in healthcare is growing, with promises that AI will reduce costs and improve efficiency, there is also concern that AI systems can perpetuate health inequalities. Prior work has explored patients’ trust in AI, but less attention has been given to how patients conceptualise the fairness of AI decision-making in healthcare and which factors influence these views. Methods We conducted a cross-sectional survey of UK patients, recruited through public and patient involvement and engagement (PPIE) networks, exploring perceptions of fairness across two AI vignettes: a patient-facing symptom checker and a clinician-facing cancer treatment decision-support tool. Respondents rated the perceived impact of 13 factors on the fairness of AI decisions and completed free-text responses to identify any additional factors. Demographics and survey variables were reported using descriptive statistics, along with Pearson’s chi-square test for differences in attitudes. Associations were estimated using ordinal logistic regression. Free-text responses were analysed thematically. Results A total of 149 respondents from the UK completed the survey. The factor perceived to most strongly undermine fairness of AI decisions was the absence of human supervision, with 89.9% of respondents reporting that AI decisions that could not be questioned by patients or clinicians would negatively impact fairness. This was followed by AI tools developed without clinician input (89.3%) and incorrect data in electronic health records (86.6%). Perceptions were consistent across both vignettes. Thematic analysis identified additional concerns not captured in the structured survey, including accessibility, the complexity of long-term conditions, ongoing maintenance of AI systems and the loss of human empathy. Conclusions Patients hold nuanced, wide-ranging concerns about fairness which span the AI lifecycle from development and deployment to maintenance. We offer design considerations, including the need for human-in-the-loop systems designed with end users and that can adapt to professional input, to support the development of fair AI systems in healthcare.