From 1960 to 1962 he was the leader of the Young Liberals, the youth wing of the Liberal Party. During the short-lived cabinet Lyng in 1963, Lerheim was appointed State Secretary in the Ministry of Church Affairs and Education. During the cabinet Borten, Lerheim again became State Secretary, this time between 1966 and 1967 at the Ministry of Finance.
He served as a deputy representative to the Norwegian Parliament from Hordaland during the terms 1965–1969 and 1969–1973. During the second term, in December 1972, Lerheim joined the Liberal People's Party which split from the Liberal Party over disagreements of Norway's proposed entry to the European Economic Community. He later served in the position of deputy representative for the Liberal People's Party during the term 1973–1977.
At the same time he became the new party leader of the Liberal People's Party, a position he held from 1973 to 1978.