Headey er født i [[Bermuda]], hvor hendes far som var politiofficerpolitibetjent, var udstationeret som rådgiver. Familien kom tilbage til Huddersfield, [[West Yorkshire]], da hun var otte år gammel. Hun fik sin første prøve som skuespiller som elev på Shelley College og fik sin første store rolle som 17 årig, da hun blev opdaget i et skoleskuespil i the Royal National Theatre, og fik en rolle som modspiller til Grant Warnock i filmen [[Waterland (film)|Waterland]] fra 1992. <ref name="headley1">[http://www.imdb.com/name/nm0372176 International movie database opslag på Lena Headley]</ref>
