The presence of nitrogen inhibits legume nodule formation, but the mechanism of this inhibition is poorly understood. We found that 2.5 mM nitrate and above significantly inhibited nodule initiation but not root hair curling in Medicago trunatula. We analyzed protein abundance in M. truncatula roots after treatment with either 0 or 2.5 mM nitrate in the presence or absence of its symbiont Sinorhizobium meliloti after 1, 2 and 5 days following inoculation. Two-dimensional gel electrophoresis combined with mass spectrometry was used to identify 106 differentially accumulated proteins responding to nitrate addition, inoculation or time point. While flavonoid-related proteins were less abundant in the presence of nitrate, addition of Nod gene-inducing flavonoids to the Sinorhizobium culture did not rescue nodulation. Accumulation of auxin in response to rhizobia, which is also controlled by flavonoids, still occurred in the presence of nitrate, but did not localize to a nodule initiation site. Several of the changes included defense- and redox-related proteins, and visualization of reactive oxygen species indicated that their induction in root hairs following Sinorhizobium inoculation was inhibited by nitrate. In summary, the presence of nitrate appears to inhibit nodulation via multiple pathways, including changes to flavonoid metabolism, defense responses and redox changes.