Gwyneth Paltrow rođena je u Los Angelesu kao dijete Brucea Paltrowa, filmskog režisera, i Blythe Danner, američke glumice. Njen otac je bio jevrejske vjeroispovijesti, a majka kršćanske. Gwyneth je pohađala privatnu školu za djevojke Spence u New Yorku, te nakratko studirala historiju umjetnosti na fakultetu u Kaliforniji, prije nego što je napustila školovanje te se odlučila posvetiti glumi. Njen mlađi brat zove se Jake. Sa 15 godina bila je zamjenska učenica u Španiji te je tako naučila govoriti španski jezik.