Fruits and vegetables are an important source of nutrients for a large number of Kenyans, as well as major earners of foreign exchange, and are commonly grown crop among smallholder farmers, who often sell them for cash. Little is known, however, about the structure of domestic demand for fruits and vegetables in this rapidly urbanizing nation and in Sub-Saharan Africa in general. We apply the Almost Ideal Demand System (AIDS) with seemingly unrelated regression (SUR) to data collected through a household expenditure survey conducted between June and July of 2009. Inelastic estimates of own-price elasticities for cabbage and tomato, and for all fruits, with the exception of onion and avocado, indicate that these are necessities. The own-price elasticities for the vegetables were negative and in the range of (-0.693) and (-0.792). The own-price elasticities for the fruits range between (-0.577) and (-1.104). Estimated cross-price elasticities also illustrate both substitutability and complementarity in demand. Expenditure elasticities above unity for kale, onion, mango and avocado suggest they are luxuries. The high expenditure elasticity of demand for some fruits and vegetables means that potential growth in demand could be large. We recommend that public investments address production and marketing systems with the aim of increasing the availability of fruits and vegetables to Nairobi households, also stimulating domestic demand for these crops among smallholder farmers.