Background: Patient waiting time in outpatient departments is a key indicator of healthcare quality, particularly in low- and middle-income countries where delays frequently exceed two hours. In Nigeria, systemic inefficiencies, understaffing, manual record-keeping, and high patient volumes contribute to prolonged waits. Existing studies have predominantly used quantitative methods, leaving a gap in understanding the lived experiences of patients and perspectives of frontline healthcare workers, especially in secondary-level public hospitals. Methods: An exploratory qualitative study was conducted at the General Outpatient Department of General Hospital Minna, Niger State, Nigeria. Convenience sampling recruited 16 patients, while purposive sampling selected 13 healthcare professionals (doctors, nurses, and health information personnel). In-depth, audio-recorded interviews were conducted and data analysed using thematic analysis. Results: Five themes emerged: patient experience and outcomes; current strategies and solutions; monitoring and metrics; implementation challenges; and future directions. Three-quarters of patients reported prolonged waits associated with emotional distress and dissatisfaction. Providers identified high patient volumes, inadequate record-keeping, and partial scheduling implementation as systemic barriers. Cultural factors influenced patient tolerance, and both groups prioritised digital solutions including electronic medical records, smart scheduling, and telemedicine. Conclusion: Waiting time in the outpatient department is shaped by interacting systemic, cultural, and operational factors. Structured monitoring, improved patient communication, and targeted digital interventions are essential to reducing delays and strengthening patient-centred care in Nigerian public hospitals.