Navnet Sudan kommer fra det arabiske bilad al-Sudan (de sortes land) som var betegnelsen de arabiske geografene i middelalderen brukte på landene sør for de muslimske områdene i Egypt og Nord-Afrika.

Kongedømmene i Nubia (grunnlagt før år 500) stod imot angrep fra den arabiske hæren som hadde erobret Egypt, og ifølge flere tradisjoner inngikk de kristne nubierne og den muslimske guvernøren i Egypt i 651/2 en fredsavtale (sulh).

Rundt 1500 ble Funjriket den dominerende staten i Nildalen; omtrent samtidig begynte en bølge med politisk sentralisering i savannebeltet mot vest. Darfur er godt dokumentert i kildematerialet fra midten av 1600-tallet. Også i Sør-Sudan var det eksempler på politisk sentralisering. Shillukene hadde en konge og kontrollerte frem til 1850 et stort område på begge sider av den Hvite Nilen, mens Azande-folket under ledelse av kriger-høvdinger ekspanderte inn i Nildalen fra vest etter 1750. De fleste etniske gruppene i Sør, som Nuer-ene og Dinka-ene utviklet imidlertid ikke overordnede politiske institusjoner, men fortsatte å være organisert i små enheter basert på slektskap og felles økonomiske interesser.

Kulturell endring kjennetegner også perioden etter antikken. I Nord-Sudan kom dette særlig til uttrykk gjennom omfattende islamisering og arabisering. Immigrasjon av arabisktalende muslimske nomader bidro i noen grad til disse prosessene, men andre faktorer var viktigere. Gjennom handel ble de økonomiske elitene delaktige i internasjonale nettverk som var preget av muslimske normer og verdier. De politiske elitene var mere skjermet for ytre påvirkning, men både Funjriket og Darfur la vekt på å tilkjennegi en islamsk identitet, til tross for at begge bygde på eldre 'afrikanske' statsdannelser. Sufi-brorskap (ar. sing. tariqa; pl. turuq) ga islam bred folkelig appell.

I perioden etter 1600 ekspanderte desentraliserte turuq som Qadiryya og Shadhiliyya, mens mer sentraliserte brorskapene som Khatmiyya, Sammaniyya og Tijaniyya har vært de største etter 1800. Islam ekspanderte ikke sør for savannebeltet (i. e. 11°-12° N). Etter åpningen av den Hvite Nilen i 1840 begynte kristen misjon i ikke-muslimske områder, men få konverterte før på 1900-tallet.

Egypt invaderte Sudan i 1820 og erobret Nubia, Funjriket og Kordofan. I 1840 fortsatte ekspansjonen med invasjonen av Taka, landskapet rundt Kassala i øst, og i 1848 ga den ottomanske sultanen kontrollen over rødehavsbyene Sawakin og Massawa til Muhammad Ali. Grensen mot sør som gikk nord for Shilluk-land, Nubafjellene og Bahr al-Ghazal, var forholdsvis stabil frem til 1860-årene da Khedive Isma'il begynte en ny ekspansjonsfase-i 1880 lå det nordligste egyptiske fortet ved Albertsjøen. Darfur som i 1874 hadde blitt erobret av al-Zubayr Pashas private hær, var det siste området som kom under egyptisk herredømme. Erobringene førte til at de områdene som i dag utgjør Sudan for første gang ble samlet til en enhet med Khartoum som hovedstad. Graden av egyptisk kontroll varierte imidlertid mye; for eksempel var store deler av Sør-Sudan (inkludert Nuba-fjellene og Bahr al-Ghazal) aldri integrert i landets administrative struktur. Hensikten med erobringene var økonomisk utbytting av Sudans ressurser til fordel for den egyptiske staten.

På 20-tallet ble de første statlige handelsmonopolene opprettet, og i flere tiår organiserte embetsmenn slaveraid inn i Sør-Sudan. Etter avskaffelsen av de siste monopolene i 1850 økte skattetrykket for bøndene. Det er tvilsomt om Egypts utgifter i Sudan ble dekket av skatter og andre inntekter, noe som ikke minst skylles utstrakt korrupsjon.

Mahdiopprøret var først begrenset til Kordofan, men spredte seg i løpet av få år til hele landet. Det egyptiske styret endte da Khartoum falt i 1885. Muhammad Ahmad ibn Abdalla al-Mahdi (1848-1885) ønsket å bygge en islamsk stat lik den profeten Muhammad hadde etablert i Arabia, men fikk støtte bare av religiøse idealister. Mahdiens etterfølger, khalifa Abdallahi (1846-1899), mislyktes i å 'eksportere' revolusjonen til Egypt og Etiopia og måtte gi opp å kontrollere Sør-Sudan. Mahdiyya-en (1885-1898) var i perioder preget av borgerkrigstilstander, og praktisk politikk var mere styrt av behovet for pragmatiske løsninger enn av ideologi.

Etter nedkjempingen av den sudanske hæren i 1898 ble Sudan et kondominium under Storbritannia og Egypt. Utenfor den sentrale Nildalen fortsatte okkupasjonsmakten å møte spredt motstand. Darfur ble ikke inkorporert i kondominiet før etter en kort krig i 1916, og deler av Sør-Sudan samt Nuba-fjellene ble ikke 'pasifisert' før etter første verdenskrig. Det nye regime opprettet en sentralisert administrasjon, men lokale ledere fikk stor makt gjennom 'indirekte styre' forordninger. Andre regler begrenset kontakt mellom Nord- og Sør-Sudan. I 1924 brukte generalguvernøren et mytteri (til støtte for Egypt) blant sudanesiske soldater som påskudd til å evakuere alle egyptere i hæren og mange i administrasjonen. I Nord-Sudan støttet staten moderniseringen av jordbruket, blant annet ved å bygge ut Geziria-prosjektet som produserte bomull for eksport. Et lite antall kvinner og menn fikk moderne utdannelse (fra grunnskolenivå til universitet). I Sør-Sudan hadde misjonskirkene ansvaret for skolevesenet og undervisningen foregikk på engelsk.

Motstanden mot kondominium-styret endret karakter etter 1920 da enkelte underoffiserer og lavere statstjenestemenn krevde selvstendighet innenfor rammen av 'Nildalens politiske enhet', dvs. fortsatt union med Egypt. Bevegelsen fikk en viss støtte i urbane strøk i Nord, men mislyktes fordi den ikke klarte å forme en allianse med Sudans tradisjonelle eliter. To hovedlinjer dominerte neste fase av den sudanesiske nasjonalismen. En gruppe, ledet av Isma'il al-Azhari som senere ble Sudans første statsminister, utnyttet forholdet til Egypt for å legge press på britene, mens andre avviste samarbeide med Egypt og forsøkte å overtale britene til stadig nye innrømmelser.

Begge gruppene hadde sterke bånd til Sudans tradisjonelle ledere; den førstnevnte til Sayyid Ali al-Mirghani som stod i spissen for det store Khatmiyya-brorskapet, den andre til Sayyid Abd al-Rahman al-Mahdi som ledet ansar-ene (de som fremdeles var lojale til mahdien og hans familie), og dannet på 40-tallet sudans første politiske partier. Forhandlinger om selvstyre begynte etter andre verdenskrig, og en lovgivende forsamling ble valgt i 1948. Etter revolusjonen i 1952 gikk Egypts nye ledere med på at Sudan fritt skulle velge mellom full selvstendighet eller union med Egypt. Det sudanesiske parlamentet som ble valgt i 1953 vedtok i desember 1955 enstemmig å erklære Sudan en selvstendig stat. Selvstendighetsakten fant sted 1. januar 1956. Sør-Sudans ledere hadde bare i liten grad deltatt i politikken på nasjonalt nivå. Allerede i 1955 gjorde soldater i Ekvatoria-provinsen opprør og innledet den første borgerkrigen som varte frem til 1972.