Nitrogenase is the only enzyme that can convert N2 into NH3. The reaction requires the addition of eight electrons and protons to the enzyme and the mechanism is normally described by nine states, E0-E8, differing in the number of added electrons. Experimentally, it is known that three or four electrons need to be added before the enzyme can bind N2. We have used combined quantum mechanical and molecular mechanics methods to study the binding of N2 to the E0-E4 states of nitrogenase, using four different density functional theory (DFT) methods. We test many different structures for the E2-E4 states and study binding both to the Fe2 and Fe6 ions of the active-site FeMo cluster. Unfortunately, the results depend quite strongly on the DFT methods. The TPSS method gives the strongest bonding and prefers N2 binding to Fe6. It is the only method that reproduces the experimental observation of unfavourable binding to the E0-E2 states and favourable binding to E3 and E4. The other three methods give weaker binding, preferably to Fe2. B3LYP strongly favours structures with the central carbide ion triply protonated. The other three methods suggest that states with the S2B ligand dissociated from either Fe2 or Fe6 are competitive for the E2-E4 states. Moreover, such structures with two hydride ions both bridging Fe2 and Fe6 are the best models for E4 and also for the N2-bound E3 and E4 states. However, for E4, other structures are often close in energy, e.g. structures with one of the hydride ions bridging instead Fe3 and Fe7. Finally, we find no support for the suggestion that reductive elimination of H2 from the two bridging hydride ions in the E4 state would enhance the binding of N2.