Enhancing local production is key to promoting food security, especially in rural households of low-income countries, but may conflict with limited natural resources and ecosystems preservation. We propose a framework integrating the water-food nexus and a sustainable livelihoods perspective to assess small-scale food production in water-poor regions. We demonstrate it by assessing alternative production scenarios in the Gaza Strip at different spatial scales. At the scale of a single farm, there is a clear conflict among objectives: while cash crops ensure good incomes but contribute scarcely to domestic protein supply, crops performing well from the nutritional and environmental viewpoint are among the worst from the economic one. At the regional scale, domestic production might cover an important fraction of nutritional needs while contributing to household income, but water scarcity impairs the satisfaction of food demand by domestic production alone. Pursuing food security under multiple constraints thus requires a holistic perspective: we discuss how a multidimensional approach can promote the engagement of different stakeholders and allow the exploration of trade-offs between food security, sustainable exploitation of natural resources and economic viability.