He was admitted to the bar in 1840 and practiced in Durham, where he was elected to his first political office as town supervisor in 1842. He was appointed District Attorney of Greene County in 1844. He was elected Surrogate in 1846, but lost reelection in 1851.
He moved to Albany, New York in 1853 and entered into partnership with former Congressman Rufus Wheeler Peckham in 1855. Elected as a Democrat, he was New York State Attorney General from 1858 to 1859.
He ran unsuccessfully as the Republican candidate for Lieutenant Governor of New York in 1862. In June 1864 he was a delegate to the Baltimore Convention of the National Union Party where he placed the name of Daniel S. Dickinson in contention for the vice presidential nomination on the ticket with President Lincoln. He served as a member of the New York State Assembly in 1866, and was elected Speaker. He was a delegate to the 1868 Republican National Convention and placed Governor Fenton's name in contention for Vice President on the ticket with General Grant.
In 1872, Tremain was elected as a Republican to the Forty-third United States Congress, defeating the incumbent Samuel Sullivan Cox. He served from March 4, 1873, to March 3, 1875, and then did not seek reelection. In 1873, Tremain also served with his partner's oldest son, Wheeler Hazard Peckham, as special counsel to the State in the prosecution of Boss Tweed. After leaving Congress, Tremain returned to private legal practice in Albany and then died in New York City while visiting. He was buried in Albany Rural Cemetery in Menands, New York.
- United States Congress. "Lyman Tremain (id: T000364)". Biographical Directory of the United States Congress.
-  The Political Graveyard
-  List of New York Attorneys General, at Office of the NYSAG
- Trial of William M. Tweed from Celebrated Trials by Henry Lauren Clinton, 1897.
|New York Assembly|
| New York State Assembly
Albany County, 2nd District
Stephen B. Cushing
| New York State Attorney General
Charles G. Myers
George Gilbert Hoskins
| Speaker of the New York State Assembly
Edmund L. Pitts
|U.S. House of Representatives|
|New district|| Member of the U.S. House of Representatives
from New York's at-large congressional seat
Henry W. Slocum