In Utah Territory, Eldredge was appointed marshal of the Territory, assessor and collector of taxes and a brigadier-general of the militia. On October 7, 1854, he was appointed one of the Presidents of the Seventy, a position he held until his death. In 1856 and 1862 he served in the Utah Territorial Legislature. He was superintendent of ZCMI for several years before his death. Eldredge practiced plural marriage and fathered 28 children. He died in Salt Lake City of lung trouble.