Abdelhaleem began his career in the Sudanese Foreign Ministry in 1975 after receiving his Bachelor of Science degree in Political Science from the University of Khartoum. In 1978, he received a master’s degree in international relations from Ohio University. He has served across Africa and the Greater Middle East for Sudan, including Saudi Arabia (1987–1989), Ethiopia (1990–1995), Somalia (1994) and Afghanistan (2003).
In an interview in a report on the conflict in Darfur by PBS's Frontline, he said, "We are a developing country, we have our shortcomings. But we are unfairly treated. The issue of Darfur has been blown out of proportion."