Constance Ernestine Berry Newman was born on July 8, 1935, in Chicago, Illinois. Her mother was a social worker and nurse and her father was a physician. Wanting to play a more active role in the civil rights movement, her father relocated the family to Tuskegee, Alabama. Newman attended Tuskegee Institute High School, located on the campus of the Tuskegee University, where she was an honor roll student and active in the Government Club. She earned her high school diploma in 1952. In 1956, Newman earned her B.A. degree in political science from Bates College, where she was active on the debate team and pre-law club. In 1959, she earned her law degree from the University of Minnesota Law School and then moved to France with her husband, who was a member of the United States Air Force.
Returning to the United States, Newman moved to Washington, D.C., in 1962, and despite having a law degree, the only employment she was able to obtain was as a clerk typist with the United States Interior Department. She remained at the Interior Department until 1967, working her way through the ranks serving as a personnel assistant and eventually personnel manager. From 1967 until 1969, Newman worked for the Office of Economic Development working with migrant farmers and then served as Special Assistant to Elliott Richardson, who headed what is now known as the Department of Health and Human Services. In 1971, she was appointed by former President Richard Nixon to serve as director of VISTA (Volunteers in Service to America), the domestic Peace Corps. From 1973 until 1976 she served as the director of the Consumer Product Safety Commission.
Between 1976 and 1977, Newman oversaw the consumer unit focused on Indian and elderly affairs as the assistant director of the U.S. Department of Housing and Urban Development. In 1977, she co-founded Newman and Hermanson Company, a consulting firm specializing in the government regulatory procedures. From 1982 until 1984, Newman worked for the Institute of American Business. In 1984, Newman served as a private consultant to on issues related to Africa, working on a World Bank project in which she lived and worked in the South African country of Lesotho. In 1989, President George H.W. Bush appointed her director of the Office of Personnel Management, and in 1992, she served as Under Secretary of the Smithsonian Institute.
In 2001, Newman was sworn is an Assistant Administrator for Africa of the United States Agency for International Development (USAID), the government agency that administers economic and humanitarian assistance worldwide. In 2004, Newman was appointed Assistant Secretary of State for African Affairs and sworn in by Secretary of State Colin Powell. She resigned in April 2005.