המצרים הרחיבו את תחום שלטונם דרומה משנות ה-20 של המאה ה-19. משלחת צבאית מצרית בפיקודו של סר סמואל בייקר האנגלי נשלחה במעלה הנילוס הלבן והגיעה לח'רטום בפברואר 1870 ולגונדוקורו (ליד העיר ג'ובה בסודאן קרוב לגבול עם אוגנדה) ביוני 1871. בייקר נתקל בקשיים מרובים והצליח להקים כמה מוצבים לאורך הנילוס בלבד. הכדיב ביקש מגורדון שיחליף את בייקר כמושל מחוז אקווטוריה (השם ניתן למחוז בשל קרבתו לקו המשווה). לאחר שהות קצרה בקהיר הפליג גורדון לח'רטום דרך סַוַכּין שלחוף הים האדום ובּרְבּר. מח'רטום הוא המשיך במעלה הנילוס הלבן לגונדוקורו.
גורדון שהה במחוז אקווטוריה עד אוקטובר 1876. הוא הצליח למפות את מקורות הנילוס, ולהקים סדרה של שתים-עשרה מצודות על הנילוס הלבן משפך הסובט ועד לגבול אוגנדה. משם הוא הציע לפתוח נתיב מזרחה למומבסה (אז בשלטון זנזיבר, בתחומי קניה של ימינו). התקדמות ניכרת נעשתה בהפסקת סחר העבדים. עם זאת, התעמת גורדון עם המושל המצרי של סודאן שישב בח'רטום. עימות זה הוביל את גורדון להודיע לכדיב על התפטרותו מהתפקיד והוא חזר ללונדון. שליט מצרים, שאורח חייו הבזבזני גרם לו לשקוע בחובות, היה זקוק לאדם ישר כגורדון שיבטיח לו הכנסה קבועה מהאזורים הנרחבים של סודאן. ב-17 בינואר 1877 שלח איסמעיל פאשה לגורדון מברק ובו הזכיר כי גורדון התחייב כלפיו כ"ג'נטלמן" והוא מצפה כי ימלא אחר הבטחתו. גורדון חזר לקהיר בפברואר 1877, אך דרש להתמנות למושל הכללי של סודאן, דרישה שהכדיב הסכים לה מיד.
סודאן – מושל כללי.
כמושל סודאן פעל גורדון בכמה נושאים. האחד היו היחסים בין מצרים לאתיופיה שהגיעו לשפל בשל מחלוקת טריטוריאלית על מחוז בוגוס. המלחמה פרצה ב-1875 והמשלחת הצבאית המצרית הובסה באופן מוחץ ב"גוּנדט". משלחת צבאית שנייה, גדולה יותר, בפיקודו של הנסיך חסן נשלחה שנה אחר כך והובסה ב"גוּרה". הסטאטוס קוו נמשך עד מרץ 1877 כשגורדון הגיע למאסאווה בתקווה להשכין שלום עם האתיופים. הוא המשיך לבוגוס וכתב למלך אתיופיה מהם התנאים המוצעים לשלום. אך הוא לא קיבל תשובה משום שהמלך האתיופי רכב דרומה למלחמה עם שבטי השואה. בראותו כי הבעיה האתיופית יכולה להמתין, חזר גורדון לח'רטום.
כמושל סודאן פרסם גורדון חוקים ותקנות שהגבילו את סמכויותיהם של הפקידים המצרים, המיסים הוקטנו ופקידי ממשל וקצינים מצרים שכשלו פוטרו ונשלחו לקהיר. המסחר פרח, וח'רטום התפתחה במהירות. גורדון מינה אירופאים לתפקידי המושלים במחוזות השונים של סודאן ובהדרגה התייצב השלטון בה.
כשמרד פרץ במחוז דארפור רכב גורדון לשם. מספרם של המורדים היה ניכר וגורדון העריך כי לדיפלומטיה יש סיכוי גדול יותר להצלחה. גורדון, שאליו התלווה מתורגמן בלבד, רכב למחנה האויב על מנת לדון במצב. פעולה נועזת זו הצליחה, שכן חלק מהמורדים הצטרפו אליו והשאר נסוגו דרומה. גורדון ביקר במחוזות של ברבר ודונגולה ואז חזר לגבול אתיופיה לפני ששב לח'רטום בינואר 1878. הוא זומן לקהיר וכשהגיע במרץ 1878 מונה לנשיא ועדת חקירה שתפקידה היה לגלות כיצד יוכל איסמאעיל לשלם את חובותיו הכספיים למלווים האירופאיים. הכדיב, שלא היה מסוגל לשלם את חובותיו, הודח על ידי הסולטאן הטורקי ב-1879 לטובת בנו תאופיק.
גורדון חזר דרומה. הוא המשיך להרר, דרומית לאתיופיה, ומכיוון שמצא שמצב המִנְהל היה בכי רע, פיטר את המושל. הוא שב לח'רטום ורכב שוב לדארפור על מנת להילחם בסוחרי העבדים. סגנו, רומולו גאסי האיטלקי, נלחם בהצלחה ודיכא מרידה שפרצה במחוז בחר אל-ע'זאל. גורדון ניסה שוב שליחות שלום לאתיופיה, שהסתיימה בכך שנלקח בשבי ונשלח בחזרה למאסווה. גורדון היה מותש משנים של עבודה בלתי פוסקת. הוא חזר לקהיר ב-2 בינואר 1880 והתפטר מהמינוי כמושל סודאן.
שנים חסרות מנוחה.
במרץ 1880 ביקר גורדון את המלך לאופולד השני בבריסל והוזמן לנהל את מדינת קונגו החופשית. באפריל, הציעה לו ממשלת מושבת הכף שבדרום אפריקה את משרת מפקד הכוחות המקומיים של המושבה. במאי ביקש המרקיז מריפון שנתמנה למושל כללי בהודו מגורדון להתלוות אליו כמזכירו האישי. גורדון קיבל הצעה אחרונה זו, אך זמן קצר לאחר הגיעו להודו, הוא התפטר. מיד אחר־כך הזמינו סר רוברט הארט, המפקח הכללי של המכס בסין, לבייג'ינג. הוא הגיע לסין ביולי ונפגש עם לי הונגג'אנג, ממנו למד כי נשקפת סכנת מלחמה בין סין לרוסיה. גורדון המשיך לבייג'ינג והשתמש במלוא השפעתו על מנת להשכין שלום. הוא חזר לאנגליה, אך באפריל 1881 עזב שוב והפעם למאוריציוס כמפקד על יחידת ההנדסה המלכותית. הוא נשאר במאוריציוס עד מרץ 1882, כשקודם לדרגת מייג'ור-ג'נרל. אחר־כך נשלח למחוז הכף על מנת להסדיר סכסוכים בבאסוטולנד, וחזר לאנגליה כמה חודשים אחר־כך.
ארץ ישראל.
בהיותו מובטל מעבודה החליט גורדון לבקר בארץ ישראל, ארץ שזמן רב רצה לבקר בה. כבר מנעוריו היה גורדון אדוק בדתו, הרבה לקרוא בתנ"ך וחפש בו רמזים לגאולת האדם. בתקופת שירותו הצבאי התחזקה בו האמונה המיסטית והוא האמין כי נועד לקיים שליחות של ההשגחה העליונה. לפיכך נסע גורדון ב-1883 לארץ ישראל ושהה כאן כשנה. בהיותו בארץ סייר באזור ירושלים כשהוא מחפש תשובות לשאלות שעלו מקריאה בספרי הקודש. גורדון טען כי המסורת המזהה את גולגולתא, מקום צליבתו של ישו, עם כנסיית הקבר הקדוש אינה נכונה וכי ישו נקבר בגן הקבר (הקרוי לכן עד היום גם הגולגולתא של גורדון). הוא כתב מאמרים בנושא, אך הסבריו לא התקבלו על דעתם של רוב החוקרים.
גורדון היה ידוע בקרב תושבי הארץ בשל מבצעיו הצבאיים בסין ובסודאן והתקבל בכבוד בקרב ערביי הארץ. עד היום נוהגים להצביע על עץ בחצר בית המוכתר של עין כרם (כיום מרכז טארג למוזיקה) שנטע במו ידיו. אבל גם בשהותו בארץ לא מצא מנוחה. במכתב מיפו לאחותו ב-1 ביולי 1883 כתב: "עברתי לכאן (מירושלים) ושכרתי בית טוב למשך 6 חודשים. מקום זה מתאים ביותר לצאת ממנו אל כל הכיוונים.". את שהותו כאן סיכם בספר "הגיגים בארץ ישראל" (Reflections in Palestine).
סודאן – מרד המהדי.
בסוף 1883 פנה מלך הבלגים לגורדון פעם נוספת והציע לו ליטול פיקוד על מדינת קונגו החופשית. גורדון קיבל את ההצעה וחזר ללונדון לערוך סידורים, אך כמה ימים לאחר הגעתו הוא נתבקש על ידי הממשלה הבריטית להמשיך מיד לסודאן, מכיוון שהמצב התדרדר שם במהירות לאחר שעזב. מרד חדש פרץ בסודאן והפעם עמד בראשו מנהיג כריזמטי, מוחמד אחמד, שהכריז על עצמו כמהדי.
בסודאן לא היו די כוחות מצריים להתמודד עם המורדים, וממשלת מצרים עצמה הייתה עסוקה בדיכוי מרד עוראבי בסיוע בריטי, שהפך את מצרים למדינת חסות למעשה. בינואר 1883 כבש צבאו של המהדי את אל-עובייד, בירת מחוז קורדופן והעיר השנייה בגודלה בסודאן, וביצע טבח באוכלוסייתה. ב-5 בנובמבר 1883 הביס צבא המהדי צבא מצרי בפיקוד בריטי שנשלח נגדו, ובדצמבר 1883 הורתה הממשלה הבריטית למצרים לנטוש את סודאן, אך פעולה זו הייתה מסובכת, כיוון שכללה נסיגה של אלפי חיילים מצרים, עובדים אזרחיים ובני משפחותיהם. הממשלה הבריטית ביקשה מגורדון להפליג לח'רטום על מנת שידווח מה השיטה הטובה ביותר לבצע את הפינוי.
ח'רטום.
גורדון יצא לקהיר בינואר 1884 בלווית קולונל ג'. ד. סטיוארט, אשר מונה לסגנו. בקהיר קיבל גורדון הוראות נוספות מהנציג הדיפלומטי הבכיר של בריטניה במצרים, סר אוולין בארינג, ומונה כמושל כללי. במסעו דרומה עבר גורדון בקורוסקו ובברבר שבקצה עיקול הנילוס והגיע לח'רטום ב-18 בפברואר. בהגיעו החל גורדון לארגן את משלוח הנשים, הילדים, החולים והפצועים למצרים וכ-2,500 איש פונו לפני שכוחותיו של המהדי חסמו את הנתיב צפונה. על פי בקשתו של גורדון, ניסה ברינג להשיג את אישורם של הבריטים והמצרים למינויו של זובאייר, מגדולי סוחרי העבדים של סודאן, אך גם מנהיג מקומי בעל השפעה, למושל סודאן לאחר שגורדון יעזוב. ברינג פעל מאחורי הקלעים להשגת המינוי, אבל גורדון, בפזיזות שנבעה מכעס בשל עיכוב האישור, דיווח לכתב "הטיימס" על הרעיון, והסערה הציבורית שפרצה בשל כך אילצה את הממשלה הבריטית לסרב לתמוך בסוחר העבדים לשעבר.
התקדמות המורדים לח'רטום השתלבה במרידה מקבילה במזרח סודאן שמנהיגה היה עות'מאן דיגנה. הכוחות המצריים בסַוַכּין שעל חוף הים האדום הובסו שוב ושוב. בשל חשש לנתיב להודו העובר בים סוף, נשלח כוח בריטי תחת פיקודו של גנרל סר ג'רלד גרהם לסַוַכּין והוא אילץ את המורדים לסגת לאחר מספר קרבות קשים. גורדון דרש כי הדרך מסַוַכּין לברבר תישאר פתוחה, אך הממשלה הבריטית בלונדון סירבה לבקשה ובאפריל פונו כוחותיו של גרהם, וגורדון וסודאן נזנחו. ב-15 במרץ מרדו השבטים שמצפון לח'רטום והצטרפו אל המהדי; הם חסמו את הנהר לתנועת ספינות וניתקו את הטלגרף שחיבר בין ח'רטום לקהיר. במאי נכנעה ברבר, וח'רטום הייתה מבודדת לחלוטין.
תחת מצור.
גורדון ארגן את הגנת ח'רטום כש-30,000 מלוחמי המהדי החלו את המצור על העיר ב-18 במרץ 1884. ח'רטום, המצויה בנקודת המפגש בין הנילוס הלבן והנילוס הכחול, הייתה מוגנת משלושה עברים על ידי הנהרות, ובהוראת גורדון נחפרה תעלה בין הנילוס הלבן לנילוס הכחול שהפכה את ח'רטום לאי. גורדון השרה תחושה של ביטחון בעיר בחודשי המצור הראשונים, קידם קצינים בדרגות, אישר הקצבות מזון מיוחדות בחגים ויישב סכסוכים. הוא הציע הצעת פשרה למהדי אך היא נדחתה בתביעה לכניעה מוחלטת.