Clemence, who was from Smithfield, Rhode Island, studied mathematics at Brown University, Rhode Island. After graduating he joined the staff of the US Naval Observatory in 1930 where he remained until 1963, serving as head astronomer and director of the Nautical Almanac from 1945 to 1958 and science director of the Observatory from 1958. In 1963 he was appointed senior research associate and lecturer at Yale, becoming professor of astronomy in 1966, a post he held until his death.

Clemence's work was primarily concerned with the orbital motions of the Earth, Moon, and planets. In 1951, in collaboration with Dirk Brouwer and W. J. Eckert, Clemence published the basic paper Coordinates of the Five Outer Planets 1653–2060. This was a considerable advance on the tables for the outer planets calculated by Simon Newcomb and George W. Hill 50 years earlier. Clemence and his colleagues calculated the precise positions of the outer planets at 40-day intervals over a period of 400 years. It was the first time that the influence of the planets on each other was calculated at each step instead of the prevailing custom of assuming that the paths of all except one were known in advance.

Such an ambitious scheme was only made possible by the emergence of high-speed computers, one of which was made available to them by IBM from 1948. For each step some 800 multiplications and several hundred other arithmetical operations were required and would, Clemence commented, have taken a human computer 80 years if he could have completed the work without committing any errors en route.

Clemence also conceived the idea that the Dutch–American astronomer Dirk Brouwer (1902–1966) named Ephemeris Time, by which time could be determined very accurately from the orbital positions of the Moon and the Earth. This followed the discovery that the Earth's period of rotation was not constant and should not therefore be used in the measurement of time. Ephemeris Time eventually came into use in 1958, although it has been superseded for most purposes by the more convenient and even more accurate atomic time scale.