Background: The healthcare industry has focused much attention on patient satisfaction with the quality of healthcare services. However, there remains a lack of research on patient satisfaction towards the implementation of an electronic medical record system at a primary healthcare setting. This study aimed at assessing the level of patient satisfaction regarding primary health care services after the implementation of an electronic medical record (EMR) system. Methods: A descriptive cross-sectional study was conducted at the Al-Wakrah health care center, with a random/convenient sample of 52 patients attending the center. Furthermore, the investigators interviewed the participants, in the waiting area, regarding their satisfaction with the primary health care services provided following the EMR system implementation. A structured interview-based questionnaire for measuring patient satisfaction was employed. Results: The vast majority of participants indicated that the overall service at the health center greatly improved after EMR implementation. Furthermore, most interviewees were totally satisfied with the overall workflow at the health care center such as the time spent at the registration desk (76.9%), before seeing a physician (65.4%), while the physician used the computer (76.9%), physical examination (69.3%), laboratory testing (73.1%), and collecting the medication (65.4%). Regarding health education and informativeness, the participants found that labeling medication bottles was quite informative. However, less than two-thirds (61.5%) of the patients were satisfied with the health education delivered by physicians. Conclusions: The results revealed that although overall patient satisfaction was relatively high, certain aspects of the health care service remained to be a source of dissatisfaction. Thus, this study demonstrated patient acceptance and support for the electronic medical record system at the primary health care setting.