Nitrogen is abundant in the earth’s atmosphere but, unlike carbon, cannot be directly assimilated by plants. The limitation this places on plant productivity has been circumvented in contemporary agriculture through the production and application of chemical fertilizers. The chemical reduction of nitrogen for this purpose consumes large amounts of energy and the reactive nitrogen released into the environment as a result of fertilizer application leads to greenhouse gas emissions, as well as widespread eutrophication of aquatic ecosystems. The environmental impacts are intensified by injudicious use of fertilizers in many parts of the world. Simultaneously, limitations in the production and supply of chemical fertilizers in other regions are leading to low agricultural productivity and malnutrition. Nitrogen can be directly fixed from the atmosphere by some bacteria and Archaea, which possess the enzyme nitrogenase. Some plant species, most notably legumes, have evolved close symbiotic associations with nitrogen-fixing bacteria. Engineering cereal crops with the capability to fix their own nitrogen could one day address the problems created by the over- and under-use of nitrogen fertilizers in agriculture. This could be achieved either by expression of a functional nitrogenase enzyme in the cells of the cereal crop or through transferring the capability to form a symbiotic association with nitrogen-fixing bacteria. While potentially transformative, these biotechnological approaches are challenging; however, with recent advances in synthetic biology they are viable long-term goals. This review discusses the possibility of these biotechnological solutions to the nitrogen problem, focusing on engineering the nitrogen symbiosis in cereals.