Paddock was born in Glens Falls, New York. His father, Ira Paddock, was a prominent lawyer. Algernon lived in upstate New York until the age of 27, attending Glens Falls Academy and Union College, teaching school and studying law. He visited a brother in Detroit, Michigan for three months after college, but then returned to New York.

In 1857, Paddock left New York, never to live there again. He settled in Omaha, Nebraska and started a farm and a law practice. He became an important member of the community, immediately entering politics as a member of the United States Republican Party in which he would be active for the rest of his life. He unsuccessfully ran for a seat in the Nebraska Territory house of representatives in 1858. He helped edit the newspaper "Nebraska Republican" from 1858 to 1859. He attended a territorial convention in 1859 and the Republican Convention as a delegate in 1860. In 1860 he campaigned heavily for Abraham Lincoln in Nebraska and New York.

In 1861, Paddock was appointed by Lincoln as secretary of the Nebraska Territory. He held that position until Nebraska became a state in 1867; he also served as acting governor in 1861. When Nebraska became a state, he ran for seats in both the United States House and United States Senate, but lost. President Andrew Johnson offered him the position of governor of Wyoming Territory, but Paddock declined that position.

In 1869, Paddock married Emma Mack, and they would have several children. In 1872 he moved from Omaha to Beatrice, Nebraska where he started a farm and a factory. In 1875, he was elected to the United States Senate. As a senator, he served as chairman of the Agriculture Committee from 1877 to 1878. He was defeated for reelection in 1880.

In 1882, Paddock became part of a commission which set up elections in Utah Territory. He used this position to try to discourage the practice of polygamy in Utah. He was a member of the commission until 1886, when he was again elected to the United States Senate from Nebraska. He served another 6-year term, from 1897 to 1893, during which he was chairman of two committees. In 1891 he introduced an unsuccessful bill to regulate certain food production for safety reasons. After his death, similar and more extensive laws on this issue were passed.

After retiring from the Senate in 1893, Paddock returned to Beatrice, where he engaged in brokerage business for four years, until he died. He died in Beatrice.