Eichholzer studierte in Graz Architektur. Von Le Corbusier beeinflusst, in dessen Atelier er 1928/29 arbeitete, schuf er in Graz und der Obersteiermark in den 30er Jahren eine Reihe von Bauten im Sinne des „Internationalen Stils“. Eichholzer engagierte sich bereits in seiner Studienzeit politisch. Der Sozialdemokrat kämpfte im Februar 1934 auf Seiten des Republikanischen Schutzbundes, wurde verhaftet und musste am 12. März fliehen. Von Paris aus folgte er im Herbst 1938 dem Ruf Clemens Holzmeisters nach Ankara, der mit Bauten für die türkische Regierung beauftragt war. 1940 kehrte er aus der Türkei zurück, um hier den kommunistischen Widerstand gegen die Nazis mitaufzubauen. Durch einen Spitzel verraten, wurde Eichholzer 1941 verhaftet, vor dem „Volksgerichtshof“ angeklagt und zum Tode verurteilt. Am 7. Jänner 1943 wurde er in Wien hingerichtet.