В 1956 г. на смену Holden FJ, который представлял собой просто модернизированную версию оригинальной модели FX 1948 г., пришёл совершенно новый автомобиль - Holden FE. Его дизайн был разработан под влиянием Chevrolet 1955 г., о чём свидетельствовали цельное лобовое стекло, козырьки на фарах, маленькие хвостовые плавники и, как правило, двухцветная окраска. Однако в сравнении с американскими машинами Holden по-прежнему выглядел скромно, несмотря на увеличение колёсной базы до 105" (2667 мм), и имел достаточно бедное внутреннее оборудование. 4-дверный седан предлагался в трёх уровнях отделки (Standard, Business и Special), 5-дверный универсал, представленный в 1957 г. - в двух (Standard и Special). Для коммерческих целей можно было приобрести ещё два варианта кузова: 2-дверный пикап Utility и фургон Panel Van.

Holden FE оснащался рядным 6-цилиндровым двигателем OHV объёмом 2262 см3 и мощностью 71 л.с. вместе со стандартной 3-ступенчатой механической коробкой передач. В отличие от предшественника, он имел 12-вольтовое электрооборудование (а не 6-вольтовое) и переднюю подвеску со стабилизатором поперечной устойчивости. С 1957 г. Holden FE выпускался не только в Австралии, но и на новом заводе General Motors в Новой Зеландии. Модель экспортировалась в Индонезию, Гонконг, Сингапур, Фиджи, Судан и ЮАР. До 1958 г. было произведено 155161 ед. Holden FE, после чего в продажу поступила его незначительно обновлённая версия под названием Holden FC (1958-1960).