Malaria remains a major public health challenge in northern Nigeria, with primary healthcare facilities (PHCs) serving as the first point of diagnosis and treatment for most patients. Despite continued investments in healthcare personnel, infrastructure, and diagnostic resources, evidence on how efficiently these inputs are converted into positive malaria treatment outcomes is limited. This study evaluates the relative efficiency of 7 PHCs across the 11 local government areas of Gombe State using data envelopment analysis (DEA). An output-oriented Variable Return to Scale (VRS) model employed to assess the ability of facilities to maximize malaria recovery outcomes given existing resource levels. Eight (8) input variables: Number of Doctors, Number of Nurses, Number of Laboratory Technicians, Personnel Salaries, Number of Beds, and Number of Patients with Fever Tested using RDT/Widal, Number of Confirmed Uncomplicated Malaria Cases and Number of RDT Test Kits Used were evaluated against a single output: The Number of Patients Recovered from Malaria. DEA results revealed significant variations in efficiency across facilities. Of the 78 facilities analyzed, 28 PHCs achieved an efficiency score of 1, representing approximately 35.9% of the sample, demonstrating optimal alignment between resource utilization and recovery outcomes. However, 50 (64.1%) facilities showed varying degrees of inefficiency characterized by underutilized staff, low diagnostic productivity, and mismatches between patient load and available beds or test kits. Maikaho Primary Healthcare Centre (DMU68) was the top performer, appearing in 50 reference sets and ranking first in efficiency. Efficient PHCs provided replicable best-practice models for improving resource deployment and treatment effectiveness across the state. The study offers actionable insights for policymakers, health managers, and the Gombe State Primary Healthcare Development Agency, particularly in strengthening diagnostic accuracy, optimizing workforce deployment, and improving malaria case management. Overall, these findings contribute to building a more effective PHC system and advancing public health outcomes in resource-limited settings. Keywords: Data Envelopment Analysis; Primary Healthcare; Malaria Treatment; Technical Efficiency