A black medic (Medicago lupulina L.) cover crop produces a persistent seed bank and self-reseeds each year in North America, but its effects on soil microbial communities are not clear. A field trial was established in 2003 with the following experimental treatments: (a) black medic or no medic, (b) a 3-year crop rotation of flax (Linum usitatissimum L.)-oats (Avena saliva L.)-winter wheat (Sativum aestavum L.), and (c) fertilizer N applied to the rotation crops at three rates: 20, 60 and 100% of the recommended N based on soil testing. In 2011, soil bacterial communities were characterized by pyrosequencing. Black medic increased Shannon and Simpson indices of diversity, and both indices increased linearly with increasing N rate. Sixteen phyla were observed and the most abundant (in bulk soil and rhizosphere, respectively) were: Actinobacteria (39.6 and 37.0%), Proteobacteria (34.0 and 32.9%), Acidobacteria (10.8 and 13.8%) and Bacteroidetes (6.2 and 6.7%). Black medic increased the abundance of Proteobacteria, but decreased the abundances of Actinobacteria and Firmicutes in bulk soil, and Acidobacteria in the rhizosphere. Bacteroidetes increased, but Actinobacteria decreased, with increasing fertilizer N rate in bulk soil. Therefore, the two predominant soil bacterial phyla, Actinobacteria and Proteobacteria, had opposite responses to black medic and fertilizer N, presumably due to differences in their ecological classifications. Soil bacterial community structures were shaped by medic. The bacterial phyla in bulk soil that were most associated with medic treatments included Proteobacteria and Bacteroidetes and those associated with no-medic treatments included Actinobacteria, Chloroflexi and Planctomycetes. The rotation crop effects were inconsistent. However, fertilizer N suppressed medic growth, so a black medic cover crop in this semi-arid region would be beneficial only in low-N or organic farming systems.