Background: Client satisfaction is considered as one of the factors that influence the use of family planning and other reproductive health services. It is very important to improve utilization of the service. Despite this importance, satisfaction still has been ignored by health care managers. Objective: The main aim of this study was to assess the level of client satisfaction with family planning service in public health centers and identify factors associated with client satisfaction in Kucha district, Gamo Gofa Zone, South Ethiopia. Methods: Facility based cross -sectional study was conducted from July 1-21, 2017 with 538 family planning service users. Respondents were selected by using systematic random sampling from four randomly selected rural health centers in the district. Data was collected by using pre-tested structured questionnaire and analyzed by SPSS version 20.0. Four diploma nurses collected the data and two B.Sc nurses supervised the data collection process. Logistic regression analyses were conducted and statistically significant association was declared at P value <0.05. Result: About 68.4% of the clients were satisfied with the service they received. Multivariable logistic regression analysis indicated that respondents with age 35 and above years [AOR (95% CI)=3.006 (1.308,6.911)], respondents who attended secondary cycle (5-8) [AOR (95% CI)=2.716 (1.377,7.817)], those for whom privacy was ensured [AOR (95% CI)=1.771 (0.738, 4.252 )], clients who received respect and friendly approach from other clinic staffs [AOR (95% CI)=6.871 (3.344,14.116)], those who reported convenient clinic opening hour [AOR (95% CI)=6.288 (2.865,13.801)] and those who got adequate information [AOR (95% CI)=5.043 (2.362,10.767)] shows significant association with the outcome variable. Conclusions and recommendations: In this study, client satisfaction is slightly high. Predictors of clients’ satisfaction with family planning service in this study were age, educational level, adequacy of information to clients, convenience of clinic opening hours, respect and friendly approaches from other clinical staffs and maintenance of privacy. Appropriate Information, education and communication is needed to solve the problem.