In 1996, the Civil Servants Union of Zambia (CSUZ) (now the Civil Servants and Allied Workers Union of Zambia (CSAWUZ) invited the National Amalgamated Local and Government Parastatal Workers Union of Botswana (NALGPWUB - unofficial abbreviation) to its conference in Livingstone, Zambia. During the conference, the two unions discussed the idea of collaboration between public service unions in the region – i.e. the Southern Africa Development Community (SADC). The unions agreed to invite the Public Services Association of Zimbabwe (PSAZ) to join efforts and to further develop on the idea. 

In 1997, the NALGPWUB invited the CSUZ and the PSAZ for a meeting in Kasani, Botswana, which resulted in establishing a collaboration. However, the cooperation was soon challenged in the NALGPWUB. An internal leadership crisis led to the emergence of splinter groups within the union. A result of subversive intervention by the Government of Botswana internally in the union. The NALGPWUB was therefore forced to leave the collaborative venture in 1998 to resolve its internal challenges.

In 1999, CSUZ invited the South African Police Union (SAPU) and the Public Services Association of Zimbabwe (PSAZ) to its Delegates Conference. At the conference union cooperation was brought back on the agenda, and the idea of bringing the three unions and their members closer together was once again brought to the union leadership. The discussions centered around the identification of activities in areas such as sharing of union strategies and joint educational programs. They agreed to meet again to further develop their strategies and see how the collaborative venture could come to fruition.

The three unions met in Pretoria, South Africa in 2000. During this meeting ideas were developed and a project proposal was submitted to the South African Research Democratic Foundation (SARDF) in Botswana with the aims of getting funding from the SARDF. At the time, the main goal was to promote internal union democracy, human rights, and workers’ rights. Following a long application process, the SARDF proposed to also include issues of HIV and AIDS. SARDF additionally encouraged the union to look for other donors to fund projects targeting specific needs of various countries’ challenges. Unfortunately, SARDF was shut down in 2001 before any funding had been secured.

Failing to obtain funding from SARDF, the General Secretary of South African Police Union, Celeste Van Niekerk approached the Public Service International (PSI).  Van Niekerk reached out to the General Secretary of the PSI, Hans Engelberts, and shared the collaborative ideas of the three unions. At this point, PSI approached YS about joining forces with the three public sector trade unions. However, 2003 was the beginning of a collaborative relationship between YS and its partners in the southern African region. YS got its funding for the project from the government of Norway through the Norwegian Agency for Development Cooperation (NORAD).

In the beginning, the name of the project was: Human rights, Trade unions rights and Democracy. When recognizing the challenges in the region, the project was given substantial help by the Royal Norwegian Embassy in Pretoria. The Embassy saw a need for this type of civil society cooperation and knowledge between important civil society institutions. Overall, the goal of the project was to strengthen trade union structures in the region, increase awareness and knowledge about human rights, and improve public services and cooperation between the involved unions. Other focus areas were also later added, such as climate change, anti-corruption, and gender related issues. The project covered South Africa, Zimbabwe and Zambia, which added up to more than 200 000 trade union members. The main activities were training and development of trade unions representatives and members, and providing knowledge to teach fellow members in the different organizations.

CSUZ, SAPU and PSAZ were soon expanded to six other public service unions from other countries in the region. The public service unions are; the National Amalgamated Local and Government Parastatal Workers Union from Botswana, the Civil Servants Trade Union of Malawi, the National Public Service, and Allied Workers Union from Swaziland, the Lesotho Trade Union Congress, the National Union of Angolan Workers, and the National Trade Union of Public Function of Mozambique

While the trade unions were completed necessary training, the leadership were equally figuring out ways in which the public-sector federation could be established to represent interests at a regional level. These discussions succeeded, hence the Federation of Southern Africa Public Sector Trade Unions (FESAPSTU) was established on August 14^th, 2014.