Родилась 7 августа 1970 г. в селе Усть-Белая Анадырского района Магаданской области (ныне на территории Чукотского автономного округа).
В 1990 г. окончила Анадырское педагогическое училище народов Севера (с 2003 г. - в составе Чукотского многопрофильного колледжа) по специальности "учитель младших классов", в 2013 г. (заочно) - Московский государственный университет экономики, статистики и информатики (в 2015 г. реорганизован путем присоединения к Российскому экономическому университету им. Г. В. Плеханова) по специальности "юриспруденция". В 2018 г. завершила обучение в Российской академии народного хозяйства и государственной службы при президенте РФ.
В 1990-х гг. работала в средней школе села Янранай (ныне упразднено; Чукотский автономный округ), затем - педагогом дополнительного образования в Певеке в том же регионе.
В 2000-х гг. Елена Евтюхова являлась председателем Совета представителей коренных малочисленных народов при администрации Чаунского района Чукотского автономного округа, а также главным специалистом, консультантом по Чаунскому району Управления по делам коренных малочисленных народов Чукотки аппарата губернатора и правительства Чукотского автономного округа. С 2009 г. курировала молодежную общественную организацию "Союз молодежи "Чаун-Чукотка".
В первой половине 2010-х гг. - ведущий, главный консультант по Чаунскому району Управления по делам коренных малочисленных народов аппарата губернатора и правительства Чукотского автономного округа. С 2013 г. являлась заместителем главы администрации Чаунского района по делам коренных малочисленных народов Севера и национальной политике.
С 2015 г. Елена Евтюхова возглавляла Управление по делам коренных малочисленных народов Чукотки аппарата губернатора и правительства Чукотского автономного округа, с 2018 г. также являлась заместителем руководителя аппарата. Входила в состав комиссии по делам несовершеннолетних и защите их прав при правительстве региона.
С 2021 г. - депутат Государственной думы РФ VIII созыва от "Единой России". Была избрана 19 сентября 2021 г. по Чукотскому одномандатному избирательному округу №224 (Чукотский автономный округ). Набрала 36,95% голосов (второе место в округе заняла Юлия Бутакова от ЛДПР, 19,87%). С 12 октября 2021 г. - член комитета Госдумы по развитию Дальнего Востока и Арктики.
Член политической партии "Единая Россия". Входит в состав регионального политсовета чукотского отделения этой партии. С 2015 г. также является руководителем Чукотского регионального координационного совета сторонников "Единой России".