Эленио Эррера родился в Буэнос-Айресе в испанской семье. Его отец, Франсиско, был изгнанным из Андалузии анархистом и работал плотником, мать, Мария Гавилан Мартинес подрабатывала уборщицей. Как и многое в его жизни, точная дата рождения будущего тренера покрыта мраком тайны. Во всех трех паспортах Эрреры (аргентинском, французском и испанском) был проставлен 1916 год рождения, но официальный сайт специалиста утверждает с его слов, что в свое время дата была сфальсифицирована и на самом деле потомок Франсиско и Марии родился 10 апреля 1910 года. Как бы то ни было, в начале 1920-х годов вся семья в поисках лучшей жизни перебралась в Касабланку – тогдашний французский колониальный город, где Эррера пошел в местную школу, отличавшуюся исключительно пестрым набором учеником. У мальчика тут же появились друзья среди евреев, испанцев, французов и итальянцев, с которыми он и начал делать свои первые шаги в футболе, играя на позиции защитника. Вскоре его заметили и пригласили в молодежную любительскую команду «Роше Нуар», откуда в 1931-м он и попал в свой первый профессиональный клуб. После сезона, проведенного в «Расинг Касабланке», Эленио отправился во Францию, где играл за «Стад Франсе», «Шарлевиль», «Эксельсиор», «Ред Стар» и «Пюто». Несмотря на то что Эррера обладал внушительными физическими данными и мог бы стать отличным защитником, травма колена в середине 1920-х помешала его футбольной карьере. Игрок постоянно подрабатывал: коммивояжером, учителем физкультуры, массажистом. В 1939-м Эррера избежал призыва, поскольку в то время работал со стеклопластиком, который был нужен для военных нужд, из-за чего футболиста оставили на производстве.
В сезоне 1944/45 Эленио был играющим тренером в «Потю», после чего с досадой повесил бутсы на гвоздь:
«В качестве игрока я был довольно печальным зрелищем. Но мое преимущество заключается в том, что великие футболисты после завершения карьеры становятся памятниками самонадеянности. Они не знают, как научить тому, что сами делали с такой легкостью и изяществом. Мне же это никогда не грозило».
Неполноценная футбольная карьера подарила Эррере повышенную восприимчивость ко всему, что происходило на поле, возможности для глубокого анализа и развития тактического ума. Он ушел из футбола, чтобы тут же вернуться в другом качестве, с готовыми теориями и концепциями, которые ему не терпелось испробовать на живых игроках. После трех сезонов во главе «Стад Франсе» Эленио перешел в «Вальядолид», с которым дошел до финала Кубка Испании, а уже через год стал главным тренером мадридского «Атлетико». Здесь в течение четырех сезонов он завоевал два чемпионских титула, после чего решил двигаться дальше, потренировав короткое время «Малагу» и «Депортиво». Затем Эррера возглавил «Севилью», с которой дважды становился четвертым и один раз вторым в Ла Лиге, а в 1957-м покинул Испанию, чтобы поработать с португальским «Белененсишем».
К тому времени методы работы аргентинца были хорошо известны на Пиренейском полуострове. Один из игроков «Атлетико» вспоминал, что перед началом выездных матчей тренер еще до выхода футболистов на поле прохаживался перед трибунами, пока болельщики хозяев тратили свои силы на крики и свист в его адрес, чтобы потом у них уже не оставалось сил и запала. Другой говорил, что они тренировались с сильнейшими физическими нагрузками ежедневно минимум по три часа, зато в воскресенье «могли уничтожить кого угодно».