As organizations grow and become multi-national, distributed work, i.e. work where members are located in different sites, cities or countries usually follows (Meyerson, Weick et al. 1996; Jarvenpaa and Leidner 1999; Zolin and Hinds 2002; Hossain and Wigand 2004; Panteli 2005). Yet, such teams and groups have fewer opportunities to build social networks as is common in traditional groups, such as time spent together and frequent informal interaction. The “paradox of trust” in distributed work then, is that while trust is a “need to have”-asset” for distributed work groups – in particular for knowledge work – it is also difficult to foster due to the lack of physical co-location (Handy 1995). This article argues that one way to deal with the paradox is to recognize the importance of trust as generated through individuals that have trustful ties that cross central boundaries; i.e. trust brokers. Based on a relational approach to trust in groups, as well as empirical studies of distributed work groups, we argue that trust brokers can help to establish trust quickly and make the group operate in more robust and sustainable ways.