Following a period of civil conflict which lasted more than a decade, Sudan is now facing multiple challenges particularly in the delivery of Primary Health Care. The effects of a long period of civil conflict on an already fragile health system impose a new threat to the health status of the people of Sudan in general and the South in particular. In addition several factors affect the delivery of health services that need to be considered for a successful health policy administration in post conflict Sudan. The disparity of the epidemiology and delivery of health services among different regions of Sudan and the factors leading to the changing faces of the AIDS epidemic in the region add to the challenges of the new administration. The paper discusses the major challenges facing the new administration in the delivery of health services, the contributing factors and finally few approaches and guidelines towards a successful health policy are presented.