Social Security Law is central to European welfare states. In the EU context, an extensive body of law lays down the legal framework on coordination of social security in Regulations (EC) 883/2004 and 987/2009, which concretise the Treaty provisions on free movement. As in other fields of European legal cooperation, questions arise on the degree of trust between the involved states, and how this affects the individuals concerned. Against this background, the contribution discusses the role of mutual trust and mutual recognition in the field of social security coordination. First, it examines the legislative choice of using coordination as the primary mode of cooperation in the field. Second, it highlights the challenges in the situations where mutual recognition is required under the Regulations, such as concerning portable documents issued in other Member States. Third, it examines the concept of mutual assistance between national administrative bodies.