In recent years, there has been an increased demand by the South African communities and society at large for public institutions to become more accountable. The literature seems to support the view that managerial trust and organisational trust in the public sector is globally acknowledged as a strategic goal. It is imperative for leaders in the public sector to recognise the nature of the business leadership that is required in the South African context. Servant leadership was identified as a leadership style that is most likely to achieve the objective of a trusting public sector.The paper examines the relationship between servant leadership and interpersonal trust, as well as organisational trust in a public sector organisation in South Africa. The sample consisted of 54 employees of the City of Johannesburg Property Company (SOC) Ltd who participated in a survey designed around the Servant Leadership Behaviour Scale developed by (Sendjaya, Sarros&Santora, 2008) along with the Organisational Trust Indicator (Nyhan&Marlowe, 1997).The results of the investigation confirmed what the literature says on servant leadership and trust. It revealed a statistically significant relationship between the opinions of servant leadership with both interpersonal trust and organisational trust. These findings will be discussed in terms of their implications for establishing what kind of leadership model might work in public sector organisations and how this approach might build trust among employees as key stakeholders.