Experiments at electron-positron colliders can search for dark matter particle pair-production in association with a photon. We estimate the sensitivity of this search at the proposed International Linear Collider (ILC), under a variety of run scenarios. We employ the effective operator formalism to provide a quasi-model-independent theoretical description of the signal, and present the reach of the ILC in terms of the scale \Lambda suppressing the dark matter-electron coupling operator. We find that at the 250 GeV center-of-mass energy, the ILC can probe \Lambda up to 1-1.2 TeV, a factor of 2.5-3 above the best current bounds from LEP-2. With 1 TeV energy and polarized beams, the reach can be extended to 3-4 TeV. The ILC can discover this signature even if annihilation to electrons provides only a small fraction of the total dark matter annihilation rate in the early universe. We also argue that large regions of parameter space allowed by current LHC and direct detection bounds will be accessible at the ILC.