Small-scale cross-border trade provides opportunities for economic gains in many developing countries. Yet cross-border traders -- many of whom are women -- face harassment and corruption, which can undermine these potential gains. This paper presents evidence from a randomized controlled trial of a training intervention that provided access to information on procedures, tariffs, and rights to small-scale traders to facilitate border crossings, lower corruption, and reduce gender-based violence along the Democratic Republic of Congo (DRC)–Rwanda border. The training reduces bribe payment by 5 percentage points in the full sample and by 27.5 percentage points on average among compliers. The training also reduces the incidence of gender-based violence by 5.4 percentage points (30.5 percentage points among compliers). The paper assesses competing explanations for the impacts using a game-theoretic model based on Hirschman's Exit, Voice, and Loyalty framework. The effects are achieved through early border crossings at unofficial hours (exit) instead of traders' use of voice mechanisms or reduced rent-seeking from border officials. These results highlight the need to improve governance and establish clear cross-border trade regulations, particularly on the DRC side of the border.