How do terrorists recruit? We know much about the profiles and pathways of recruits, but little about the strategies and tactics of recruiters. Such procedures matter because they help determine who joins. I highlight a key determinant of recruiter tactics, namely, the tension between personnel needs and infiltration risks. Drawing on signalling theory, I present an analytical framework that conceptualizes recruitment as a trust game between recruiter and recruit. I argue that the central logic shaping recruiter tactics is the search for cost-discriminating signs of trustworthiness. Due to the context-specificity of signal costs and the room for tactical innovation, optimal recruitment tactics vary in space and time, but the underlying logic is the same for most groups facing a high threat of infiltration. I apply the framework to an al-Qaeda recruitment campaign in early 2000s Saudi Arabia, where it helps explain tactical preferences (why recruiters favoured some recruitment arenas over others) and differential network activation (why recruiters preferred war veterans over radical candidates from other networks). The trust dilemma also accounts for unexpected recruiter choices, such as their reluctance to solicit on the Internet and in mosques, and their preference for recruits who knew poetry or wept during prayer. Thus the signalling framework does not challenge, but provides a useful micro-level complement to, existing theories of recruitment.