The United States has repeatedly debated whether to adopt a nuclear no-first-use (NFU) pledge. Advocates for such a pledge emphasize its potential advantages, including strengthening crisis stability, decreasing hostility, and bolstering nonproliferation and arms control. But these benefits depend heavily on nuclear-armed adversaries finding a U.S. NFU pledge credible. A new theory based on the logic of costly signals and tested on evidence from NFU pledges by the Soviet Union, China, and India suggests that adversaries perceive such pledges as credible only when: (1) the political relationship between a state and its adversary is already relatively benign, or (2) the state's military has no ability to engage in nuclear first use against the adversary. Empirically, these conditions rarely arise. More typically, hostile political relations combined with even latent first-use capabilities lead adversaries to distrust NFU pledges and to assume the continued possibility of being subject to first use. The implication is that changes to U.S. declaratory policy alone are unlikely to convince adversaries to disregard the prospect of U.S. nuclear first use without changes in these countries’ political relationships or U.S. nuclear force posture. The beneficial effects of an NFU pledge are therefore likely to be more minimal than advocates often claim.