The umpteenth threats to change of healthcare provider by dissatisfied patients on formal sector health insurance are well known and can be a proxy indicator for the need for quality improvement in service delivery. This study was aimed at evaluating patients' satisfaction with quality of care provided at the National Health Insurance Scheme (NHIS) clinic of a tertiary hospital in South-Eastern Nigeria. This was a descriptive study carried out on 400 NHIS patients from April 2011 to October 2011 at the general outpatient department of Federal Medical Centre, Umuahia. Patients were selected by simple random sampling using every second NHIS patient that registered to see the clinicians and who met the selection criteria. Data were collected using pretested, structured interviewer-administered questionnaire. Each satisfaction item was scored in a five-point Likert scale ordinal response, which was converted to percentage scale response. Satisfaction was measured from the following domains: accessibility, patient waiting time, patient-provider communication, patient-provider relationship, hospital bureaucracy, and hospital environment. Operationally, patients who scored 50% and above in the assessed domain were considered satisfied while those who scored less than 50% were dissatisfied. The overall satisfaction score of the respondents was 66.8%. Specifically, the respondents expressed satisfaction with patient-provider relationship (81.5%), patient-provider communication (79.9%), accessibility (74.2%), and hospital environment (68.2%) and dissatisfaction with hospital bureaucracy (48.8%) and patient waiting time (48.3%). This study has shown that the overall patients satisfaction with the services provided was very good with patient-provider relationship rated highest and patient waiting time the lowest. There is need to improve on the current level of patients satisfaction while effort should be made to address the identified domains of dissatisfaction.