We determined the nutritional status of children less than five years of age in an area in rural western Kenya with intense malaria transmission, a high prevalence of severe anemia and human immunodeficiency virus, and high infant and under-five mortality (176/1,000 and 259/1,000). No information is available on the prevalence of malnutrition in this area. Three cross-sectional surveys were conducted between 1996 and 1998 to monitor the effect of insecticide-treated bed nets on child morbidity. Anthropometric indices are presented for 2,103 children collected prior to and during intervention (controls only). The prevalence of stunting (Z-scores for height-for-age [HAZ] <-2), wasting (Z-scores for weight-for-height [WHZ] <-2) and being underweight (Z-scores for weight-for-age [WAZ] <-2) was 30%, 4%, and 20%, respectively. This was severe (Z-score <-3) in 12% (stunting), 1% (wasting), and 5% (underweight) of the children. Few children less than three months of age were malnourished (<2%), but height-for-age and weight-forage deficits increased rapidly in children 3-18 months of age, and were greatest in children 18-23 months old (44% stunted and 34% underweight). While the mean HAZ and WAZ stabilized from 24 months of age onwards, they still remained substantially below the reference median with no evidence of catch-up growth. Malnutrition is likely to interact with infectious diseases, placing children 3-24 months of age at high risk of premature death in this area.