Walter Frodl promovierte im Juli 1930 an der Universität Graz in den Fächern Kunstgeschichte und Archäologie. Anschließend arbeitete er als Volontär für das Kärntner Landesdenkmalamt. Nachdem Frodl einige Semester Architektur an der Technischen Hochschule in Graz studiert hatte, folgte seine Anstellung in der Zweigstelle des Österreichischen Verkehrsbüros in Klagenfurt. Im Mai 1933 trat er der NSDAP bei. Als wissenschaftlicher Assistent setzte er im Dezember 1936 seine Tätigkeit im Bereich der Denkmalpflege fort und wurde im April 1937 als nicht ständiger Vertragsbeamter der Zentralstelle für Denkmalschutz dem Landeskonservatorat in Klagenfurt zugeteilt, dessen Leitung er im folgenden Jahr übernahm. Aufgrund der enormen Anzahl an Ausfuhransuchen und der damit verbundenen Überprüfungen der Kunst- und Kulturgüter, u. a. als Konsequenz der Verfolgung von Jüdinnen und Juden durch das NS-Regime, wurde Walter Frodl im Juli 1938 aushilfsweise dem Ausfuhrdienst der Zentralstelle in Wien zugeteilt, zeitweilig übernahm er auch die Mitbetreuung des Landeskonservatorates Salzburg. Zwei Jahre später folgte seine Tätigkeit für die Kulturkommission in Südtirol im Auftrag der SS-Forschungseinrichtung "Deutsches Ahnenerbe e. V." zur Aufnahme des deutschen Kulturgutes. Ab dem Winter 1941 war Walter Frodl als Berater für Denkmalpflege beim Bau der Reichsautobahnen beim Generalinspektor für das deutsche Straßenwesen, Fritz Todt, im Einsatz. Nach der Umstrukturierung und der Umbenennung der Zentralstelle für Denkmalschutz im Ministerium für innere und kulturelle Angelegenheiten in das direkt dem Reichsministerium für Wissenschaft, Erziehung und Volksbildung in Berlin unterstellte Institut für Denkmalpflege 1940, wurden die einzelnen Gaukonservatorate in die jeweiligen Reichsstatthaltereien eingegliedert. Die Tätigkeit Walter Frodls als Gaukonservator für Kärnten erfolgte nebenamtlich. Im Februar 1942 ernannte ihn Friedrich Rainer, Gauleiter und Reichsstatthalter in Kärnten, zum Direktor des Gaumuseums in Klagenfurt und zum Beamten auf Lebenszeit. Ende des Jahres 1942 habilitierte er sich und wurde Dozent für Kunstgeschichte und Denkmalpflege an der Universität Graz bzw. Lehrbeauftragter für Denkmalpflege an der Technischen Hochschule in Graz. Von September 1943 bis Kriegsende war Frodl der Beauftragte für den Denkmalschutz in der Operationszone Adriatisches Küstenland.

1946 entließ die Kärntner Landesregierung Walter Frodl nach § 14 Verbotsgesetz als "Illegalen" aus dem öffentlichen Dienst, hob die Entlassung aber im Juni 1947 rückwirkend auf und schied Frodl aus dem Dienststand der Kärntner Landesregierung aus. Laut Bescheinigung des Magistrats Klagenfurt vom 25. Juli 1947 war Frodl als minderbelastet eingestuft worden. Zur gleichen Zeit wurde ihm seine Venia legendi aberkannt. In der Person Otto Demus fand er allerdings einen Fürsprecher für sein Ansuchen, wieder in die Denkmalbehörde aufgenommen zu werden. Sein Wiedereinstieg in den Denkmalbetrieb erfolgte vorerst auf Werkvertragsbasis in der Restitutionsabteilung des Bundesdenkmalamtes, bis er im Herbst 1948 die Agenden des Landeskonservators für die Steiermark übernahm. 1948 konnte Walter Frodl – nach Rückerlangung der Venia legendi – seine Lehrtätigkeit im Fach Denkmalpflege an der Technischen Hochschule in Graz wiederaufnehmen. Seine Lehrbefugnis an der Karl-Franzens-Universität Graz erlangte er ein Jahr später zurück. Ab 1952 war Walter Frodl als Leiter des Instituts für Österreichische Kunstforschung am Bundesdenkmalamt tätig. Im gleichen Jahr erfolgte seine Ernennung zum Staatskonservator II. Klasse, zwei Jahre später zum Staatskonservator I. Klasse. 1956 erhielt er die Lehrbefugnis für die Technische Hochschule in Wien, wo er 1958 zum außerordentlichen Professor ernannt wurde. Seine universitäre Laufbahn im Bereich Kunstgeschichte, Denkmalpflege und Bauaufnahme setzte er in den Folgejahren an verschiedenen ausländischen Universitäten fort. Neben der Ausübung weiterer Funktionen wie jener des Fachbeirates für Stadtplanung in Wien oder als Mitglied der Prüfungskommission "Höherer Technischer Dienst" übernahm Walter Frodl 1965 bis 1970 die des Präsidenten des Bundesdenkmalamtes. Im Oktober 1970 erhielt er das große Ehrenzeichen für Verdienste um die Republik Österreich.