A strategic transformation process of a Swedish agency, i.e. the Swedish Public Employment Service, is discussed from a trust framework. Lately, the agency has been heavily criticized internally (by managers and employees) and externally (by different stakeholders) for failing in fulfilling its goals and deliver inadequate services. In 2014, the agency launched a new strategy – to become trustworthy and to deliver better services to its customers. It was the agency’s attempt to move away from the old authoritarian bureaucratic management style towards introducing trust-based management control. The old and the new way of managing the agency creates tensions that are difficult to overcome and where mistrust at different levels within the organization is a major obstacle affecting the ongoing transformation process. The aim of this paper is to shed light on how trust is reconstructed in vertical and horizontal relationships within a public service delivery agency that experiences an extensive transformation process. Drawing upon a processual case study approach, we have conducted 65 interviews, observations and document studies. The results show how the agency have suffered from low levels of trust in both vertical and horizontal relationships and that low levels of trust in vertical relationships seem to have negative impact on horizontal collaborations within the agency. The paper contributes to previous research in the following ways. First, the reconstruction of trust is discussed from a time perspective, pointing at the importance of discussing the development of trust in terms of a past, a present and a future. Second, within the paper, trust is discussed in both vertical relationships (i.e. relationships between employees/managers) as well as horizontal relationships (i.e. relationships between co-workers) within the same analytical framework, which enables a discussion about the impact of trust development in vertical relationships on the development of trust in horizontal relationships and vice versa.