In this paper, we describe a novel methodology which employs machine learning as an alternative means to explore hospital characteristics and client satisfaction, for decision making and improved quality of care. We applied well known feature selection and data mining algorithms such as forward selection and Naïve Bayes respectively, to determine patient satisfaction, which is an important indicator of quality of care in hospital settings. Our dataset comprised of three types of data, (i) patient perception about received care, (ii) nurse perception about the working environment and (iii) organizational attributes of the hospital. Our experimental results exhibited high classification accuracy (87%), allowing valid conclusions to be reached about the organizational and workforce factors which attribute to patient satisfaction. Our findings were validated using traditional statistical methods such as binomial correlation and linear regression.