Food nitrogen (N) and phosphorus (P) footprints are indicators for determining the losses of N and P over food production (FP) and food consumption (FC) chain. Yemen is an interesting case because, given the country’s heavy dependence on food imports, food insecurity, and poverty, the N footprint (NF) and P footprint (PF) could affect its future development. However, NF and PF over time have not yet been studied in Yemen. Therefore, this is the first paper to compute the NF and PF in Arabian Peninsula (a case study from Yemen) by an adjusted model of N-Calculator, by computing virtual N (VNFs) and virtual P (VPFs) factors for main foodstuffs. The NF (kg N cap−1 year−1) and PF (kg P cap−1 year−1) elevated from 5.56 and 1.20 in the 1960s to 15.2 and 4.79 during 2011–2017, respectively, while the national NF (Gg [109 g] N year−1) and national PF (Gg P year−1) increased from 27.7 and 6.77 in the 1960s to 358 and 122 during 2011–2017, respectively. Cereal was the largest contributor to the NF and PF in Yemen over the past 57 years. FP contributes approximately 80% and 86% of the total NF and PF during 2011–2017. Therefore, if possible, the best way for consumers and farmers in Yemen to decrease NF and PF is to focus efforts on increasing FP and FC of foodstuffs with less VNFs and VPFs. The consumption of vegetable-fruit, legumes, starchy, eggs, poultry, and fish should be increased as their NF and PF are low. However, people in Yemen suffer from shortage of resources and lack of awareness, and thus they do not have the opportunity to choose foodstuffs that are low in NF and PF. Accordingly, policymakers should encourage integrated approaches that introduce powerful tools for controlling crop and livestock production in conjunction with enhancements in nutrient use efficiency