Early nutrition in animals affects both behavior and brain structure. In humans, randomized trials show that early nutrition affects later cognition, notably in males. We hypothesized that early nutrition also influences brain structure, measurable using magnetic resonance imaging. Prior research suggested that the caudate nucleus may be especially vulnerable to early environment and that its size relates to IQ. To test the hypothesis that the caudate nucleus could be a neural substrate for cognitive effects of early nutrition, we compared two groups of adolescents, assigned a Standard- or High-nutrient diet in the postnatal weeks after preterm birth. Groups had similar birth status and neonatal course. Scans and IQ data were obtained from 76 adolescents and volumes of several subcortical structures were calculated. The High-nutrient group had significantly larger caudate volumes and higher Verbal IQ (VIQ). Caudate volumes correlated significantly with VIQ in the Standard-nutrient group only. Caudate volume was influenced by early nutrition and related selectively to VIQ in males, but not in females. Our findings may partly explain the effects of early diet on cognition and the predominant effects in males. They are among the first to show that human brain structure can be influenced by early nutrition.