Reported here is the Pd-catalyzed C-N coupling of hydrazine with (hetero)aryl chlorides and bromides to form aryl hydrazines with catalyst loadings as low as 100 ppm of Pd and KOH as base. Mechanistic studies revealed two catalyst resting states: an arylpalladium(II) hydroxide and arylpalladium(II) chloride. These compounds are present in two interconnected catalytic cycles and react with hydrazine and base or hydrazine alone to give the product. The selectivity of the hydroxide complex with hydrazine to form aryl over diaryl hydrazine was lower than that of the chloride complex, as well as the catalytic reaction. In contrast, the selectivity of the chloride complex closely matched that of the catalytic reaction, indicating that the aryl hydrazine is derived from this complex. Kinetic studies showed that the coupling process occurs by rate-limiting deprotonation of a hydrazine-bound arylpalladium(II) chloride complex to give an arylpalladium(II) hydrazido complex.