The purpose of this paper is to discuss the organizational performance and entrepreneurial orientation of Malaysian Small and Medium Enterprises (SMEs). Literature has shown that leadership and entrepreneurial orientation are important for organizational performance but still inadequate. Thus, this investigation hopes to close this gap in the literature and contribute to a new understanding of relationships between leadership and organizational performance, and entrepreneurial orientation served as a mediator. This study comprised a sample of owners or managers in the manufacturing and service sectors of SMEs located in Kuala Lumpur and Selangor, as their largest representation of SME establishments and significant contributions to Malaysia economy. A cross-sectional research design was used to examine the relationships between leadership behavior, entrepreneurial orientation and organizational performance among SMEs. The respondent’s lists were sought from the SME Corp. Malaysia at http://www.smecorp.gov.my and http://www.smeinfo.com.my. Data were gathered based on a mailed questionnaire and personal administered questionnaires. The findings indicate that entrepreneurial orientation acted as a partial mediator in the relationship between leadership behavior and organizational performance. Transformational leadership and transactional leadership were found to have a significant relationship with entrepreneurial orientation and organizational performance of SMEs. An important implication of this research indicated that both transformational and transactional leadership behavior positively increased the individual outcome and lead to higher organizational performance.