Using the infinitely repeated prisoners' dilemma game as a modeling platform, we examine how domestic political institutions affect the ability of nations to trust and cooperate with each other. We propose a strategy, the agent-specific grim trigger, in which national leaders direct punishments for past defections at the leader of the nation responsible rather than at the nation itself. Leaders refuse to cooperate with those leaders who have cheated them in the past. However, by being prepared to cooperate with new leaders, cooperation can be restored. The focus of punishment on specific agents of the people (leaders), rather than the nation itself, means that citizens want to remove leaders who defect. Hence, domestically accountable leaders pay audience costs for failing to cooperate. These costs make accountable leaders more trustworthy and foster greater cooperation. In contrast, when replacing leaders is difficult, cooperation is less robust; and once cooperation falters, agent-specific punishment policies often lead to prolonged hostilities and periods of acrimonious relations between states.