Legitimacy is conceptualized as subjective individual attitudes and expectations about formal institutional authority and is often thought of as a reservoir of trust or goodwill that formal governing authorities draw on to secure acceptance and compliance with the law. Recent public opinion surveys in predominantly Muslim countries report declining support for U.S. government and policy, as well as increasing support for Muslim-based groups that attack the United States. Based on prior research within the United States showing that perceptions of legitimacy are related to both acceptance and compliance with the law, we examine whether perceptions about the legitimacy of the U.S. government may also be related to support for anti-American transnational terrorist attacks. Using data from more than 3,600 face-to-face interviews with respondents from three Muslim countries, we examine the effects of support for the American government, people, and culture on support for Muslim-based groups that attack Americans. In addition, we examine the effects of perceived domestic institutional legitimacy on support for Muslim-based groups that attack Americans. Our results indicate that individuals who have more favorable attitudes toward American citizens and culture are less likely to support attacks against Americans by Muslim-based groups. We also find that perceived legitimacy in one’s own political institutions, including government, police, and the criminal justice system, is associated with lower levels of support for groups that attack Americans. We discuss the implications of the results for research and policy.