Withee was born on October 26, 1834 in Somerset County, Maine. He moved to Wisconsin in 1853, settling in La Crosse, Wisconsin. In 1868, he married Louisa H. Smith. They would have one son. Withee died from a stroke in 1910.
Withee was a member of the Senate from 1893 to 1901. He was a stalwart Republican, always opposed to Robert La Follette's progressives. He was a delegate to the 1900 Republican National Convention.