Заняв четвертое место в чемпионате Португалии, Эррера вернулся в Испанию, поскольку «Барселона», обеспокоенная доминированием мадридского «Реала», искала возможность сместить «сливочных» с их трона и сделала тренеру крайне выгодное предложение. Каталонцы выигрывали Ла Лигу в начале 1950-х, но затем Королевский клуб усилился с приходом Альфредо Ди Стефано, и баланс сил в Испании сместился в сторону столицы. Мадридцы становились чемпионами страны в 1954, 1955, 1957 и 1958 годах, лишь один раз отдав титул «Атлетико», не говоря уже о трех подряд Кубках европейских чемпионов, куда «Барса» даже не квалифицировалась, поскольку в те годы в главном клубном противостоянии Старого Света играли лишь действующие обладатели золотых медалей чемпионатов. Ситуация была обескураживающей для каталонцев, несмотря на то что в их составе блистали великолепный Луис Суарес, единственный испанец, получавший «Золотой мяч», и один из лучших плеймейкеров в истории футбола, а также венгр Ладислав Кубала, к которому только что присоединились двое его соотечественников: Шандор Кочиш и Золтан Цибор, футболисты венгерской «Золотой команды». Правда, лучший игрок той сборной, Ференц Пушкаш, в том же году пришел в мадридский «Реал», а Ди Стефано стоил троих. В клубе, по воспоминаниям Эрреры, царила атмосфера уныния, тем более что и сам тренер восхищался великим аргентинцем:
Приступив к работе с командой, Эленио Эррера прежде всего постарался избавить своих игроков от пораженческого менталитета и устроил настоящий военный режим. В первые месяцы футболисты тренировались по три раза в день, причем уже во время первой тренировки аргентинец доводил их до рвоты интенсивностью физических упражнений. Тренер никогда не улыбался и не шутил во время работы с игроками, мог обозвать любого из них «мешком дерьма», если он не выполнял практически нереальный норматив, и никому никогда не давал поблажек. Если футболист во время тренировки подходил к Эррере, чтобы пожаловаться на плохое самочувствие, он тут же получал дополнительные упражнения. Когда кто-то появлялся с гипсовой или фиксирующей повязкой, тренер справлялся в медицинской службе клуба о характере повреждения, и, если это был не перелом, повязки срывались. Кроме того, специалист вникал во все аспекты личной жизни игроков, советуя им поменьше заниматься сексом в преддверии игр, и внимательно следил, чтобы проблемы на любовном фронте не мешали концентрации его футболистов.
Однажды тренерскому штабу стало известно о подруге одного из игроков, которая требовала повышенного внимания к себе, что явно отвлекало ее ухажера. По настоянию Эрреры клуб нанял частных детективов, которые выяснили, что у пары действительно напряженные отношения, а девушка даже откровенно провоцирует своего парня, встречаясь с другими мужчинами. Эленио незамедлительно предложил найти кого-нибудь, кто переспит с ней, чтобы представить доказательства измены своему футболисту. В итоге дело ограничилось мотивационными беседами и дополнительными тренировками. Эррера был действительно хорош в психологии, тонко чувствуя, что конкретно нужно тому или иному футболисту в данный момент. Когда во время одной из длительных поездок Цибор, ненавидевший находиться вне дома, пожаловался тренеру, тот спокойно заявил, что, если Золтан забьет три мяча в следующем матче, он сможет поехать домой. Назавтра венгр сделал хет-трик. Эррера признавался, что темы его мотивационных бесед с футболистами «Барселоны» могли быть самыми разными. Каталонцев он убеждал отстаивать честь Каталонии, иностранцев прельщал деньгами, с семейными обсуждал чувство гордости их жен и детей, с холостыми – возможность привлечь внимание женского пола. У тренера были самые разные сведения о всех его игроках, он мог рассказать историю семьи до третьего поколения каждого из них и собирал любую информацию, которая могла помочь мотивации футболистов.