In 1896 Sutherland, a Republican, joined the first Utah House of Representatives. In 1899 he was admitted to the bar of the United States Supreme Court, and from 1900 to 1903 he served as Utah's only Representative in the U.S. House. He then served in the U.S. Senate from 1905 to 1916. During this period, he supported much progressive legislation, including a Utah law for an eight-hour day in the mining and smelting industries, as well as national statues such as the Pure Food and Drug Act.

Defeated for the Senate nomination in 1916, Sutherland went into private law practice, served as president of the American Bar Association, and became an advisor to Republican presidential hopeful Warren G. Harding in the campaign of 1920. Harding's election and the sudden resignation of a Supreme Court justice in 1922 paved the way for Sutherland's appointment to the bench.