Der 1880 im schwedischen Täfvelsås als Sohn dänischer Eltern geborene Ernst Johan Zeuthen schlug nach der Schule trotz früher künstlerischer Neigung eine konventionelle Laufbahn ein und beendete 1903 seine Ausbildung zum Schiffsingenieur in Göteborg. In den folgenden Jahren arbeitete der junge Mann u.a. in Glasgow (wo erste Radierungen entstanden) und auf einer Werft in Flensburg als technischer Zeichner. In den Jahren 1906 bis 1908 hielt sich Zeuthen zu einem Arbeitsaufenthalt in den USA auf, wo er Ende 1906 den Entschluss faßte, dem Schiffsbau den Rücken zu kehren und eine zweite Karriere als Maler zu versuchen. Im Anschluss an seine Rückkehr nach Dänemark nahm er 1908/09 Zeichenunterricht bei der Malerin und Kunsthandwerkerin Agnes Jensen. Ab 1909 besuchte er die von Johan Rohde geleitete „Kunstnernes Frie Studieskoler“ (Freie Künstlerschule), die als eine der wichtigsten Institutionen für die Entwicklung der modernen dänischen Kunst gilt. Insbesondere durch den bekannten Maler und Miterneuerer des skandinavischen Kunsthandwerks Rohde kam Zeuthen hier mit den zeitgenössischen Kunstströmungen des Kontinents in Berührung und erlangte durch diese wichtige Impulse für seine weitere Künstlerkarriere. Insbesondere Paul Cézanne und sein von Paul Gauguin beeinflusster Landsmann Jens Ferdinand Willumsen können hier als Inspiration genannt werden. Eine erste Italienreise 1910/11 weckte darüber hinaus seine Begeisterung für die italienische Frührenaissance (Giotto, Pierro dellan Francesca u.a.).