Northeast Africa forms an interesting case study for investigating the relationship between changes in environment and agriculture. Major climatic changes in the early Holocene led to dramatic changes in the environment of the eastern Sahara and to the habitation of previously uninhabitable regions. Research programs in the eastern Sahara have uncovered a wealth of archaeological evidence for sustained occupation during the African Humid Period, from about 11,000 years ago. Initial studies of faunal remains seemed to indicate early shifts in economic practice toward cattle pastoralism. Although this interpretation was much debated when it was first proposed, the possibility of early pastoralism stimulated discussion concerning the relationships between people and animals in particular environmental contexts, and ultimately led to questions concerning the role of agriculture imported from elsewhere in contrast to local developments. Did agriculture, or indeed cultivation and domestication more generally (sensu Fuller & Hildebrand, 2013), develop in North Africa, or were the concepts and species imported from Southwest Asia? And if agriculture did spread from elsewhere, were just the plants and animals involved, or was the shift part of a full socioeconomic suite that included new subsistence strategies, settlement patterns, technologies, and an agricultural “culture”? And finally, was this shift, wherever and however it originated, related to changes in the environment during the early to mid-Holocene? These questions refer to the “big ideas” that archaeologists explore, but before answers can be formed it is important to consider the nature of the material evidence on which they are based. Archaeologists must consider not only what they discover but also what might be missing. Materials from the past are preserved only in certain places, and of course some materials can be preserved better than others. In addition, people left behind the material remains of their activities, but in doing so they did not intend these remains to be an accurate historical record of their actions. Archaeologists need to consider how the remains found in one place may inform us about a range of activities that occurred elsewhere for which the evidence may be less abundant or missing. This is particularly true for Northeast Africa where environmental shifts and consequent changes in resource abundance often resulted in considerable mobility. This article considers the origins of agriculture in the region covering modern-day Egypt and Sudan, paying particular attention to the nature of the evidence from which inferences about past socioeconomies may be drawn.