ב-18 בדצמבר הציע סגן שר החוץ הבריטי תומאס סנדרסון להרצל, שהציונים ישגרו משלחת לחקור את התנאים בחצי האי סיני, ואם הדין וחשבון יהיה חיובי, ניתן יהיה לדון בהקמת מושבה יהודית שם. המתיישבים יצטרכו לוותר על נתינותם המקורית ולהיות כפופים לשלטון המצרי (למעשה בריטי), ולשלם לממשלת מצרים תשלום שנתי תמורת שמירת הסדר. בינואר 1903 הגיע הרצל ללונדון, ויחד עם גרינברג נועד עם סנדרסון במשרד החוץ. בפגישה סוכם הרכב המשלחת ותוכנית המסע שלה. כעבור שבועיים הגיעה המשלחת למצרים, וב-11 בפברואר חצתה את תעלת סואץ בקנטרה ופנתה צפונה לאל עריש. גרינברג נשאר בקהיר לדון עם הממשלה המצרית על פרטי הזיכיון. ב-16 בפברואר הודיע גרינברג להרצל כי נציג הסולטאן בקהיר מנסה לחבל בתוכניתם. למחרת היום הודיע פתאום כי אין סיכוי כרגע להשיג צ'ארטר, והציע לקרומר תוכנית חדשה. ב-26 בפברואר הודיע להרצל שקיבל מבוטרוס ראלי מסמך המתיר את כינונה של "רשות עירונית" יהודית באל עריש. ב-16 במרץ הגיע גרינברג לווינה ודיווח להרצל על המשא ומתן. הרצל לא סמך עליו עוד, ובאותו לילה יצא למצרים. ב-25 במרץ נפגש בקהיר עם קרומר, שהביע הסתייגות מתוכניתו של הרצל והדגיש כי המתיישבים יזכו לכל היותר בממשל מוניציפלי. הרצל נסע משם למשרד ראש הממשלה והסביר לבוטרוס ראלי שאת המים לסיני יביא מהנילוס – רק את מי הנהר הזורמים עתה לים, שיאוחסנו במאגרים. ראלי הביע הסכמה מלאה לכל דבריו. המשלחת שבה לקהיר עם ממצאים מעודדים, אולם סיכמה כי לא ניתן להתיישב ללא "כמויות מים מספיקות". הרצל ומומחי המשלחת נועדו מספר פעמים עם קרומר. הרצל הציע להעביר את מי הנילוס בצינור תחת תעלת סואץ. המומחה הבריטי להשקיה טען כי יש די מים בנילוס לספק גם את צורכי מצרים וגם את צורכי המושבה שתקום בסיני, אולם קרומר סירב להחליט בנושא לפני חזרתו למצרים בחודש מאי של ויליאם גארסטין, המומחה שלו לענייני עבודות ציבוריות. עם זאת, ביקש מהרצל לפתוח במשא ומתן עם הממשלה המצרית על הפרטים המשפטיים. הרצל פנה לפרקליט בלגי מקומי והורה לו להכין טיוטת הסכם לחכירת סיני ל-99 שנים. ב-4 באפריל עזב הרצל את מצרים והגיע ללונדון להיפגש עם צ'מברלין. צ'מברלין אמר לו שהוא לא מעודד מממצאיו של דו"ח המשלחת, והציע תחליף: "במסעי האחרון באפריקה ראיתי ארץ אחרת שתתאים לך. אוגנדה!". אולם הרצל דחה את ההצעה והסביר כי בסיס ההתיישבות צריך להיות לאומי ולכן הכרחי שיהיה בתוך ארץ ישראל או בקרבתה. במאי 1903 הטיל גארסטין וטו על תוכנית סיני, משום שלדעתו אין די מים בנילוס. קרומר סבר, כי בכל מקרה מחיר שאיבתם לסיני מתחת לתעלת סואץ יהיה יקר מדי, ויתרה מזאת, בניין המשאבות יפריע לתנועת האוניות בתעלת סואץ וכתוצאה מכך ישבש את המסחר הבריטי עם המזרח הרחוק. הרצל הבין כי תוכנית סיני מתה, ואף איבד תקווה לגבי מימושה הקרוב של תוכניתו ליציאת היהודים מאירופה. הוא הוציא את אביו מקברו וטמן אותו באחוזת קבר חדשה שרכש. בזמן הטקס ליד הקבר, לחש למזכירו: "עוד מעט אשכב פה גם אני".
בעקבות פרעות קישינב.
ב-19 באפריל 1903 פרצו פרעות קישינב. הרצל שמע על כך כששהה בלונדון, לפני פגישתו האחרונה עם צ'מברלין. דחייתה הסופית של תוכנית סיני בתחילת מאי גרמה לו לחפש פתרון אחר למצוקת יהודי רוסיה, ולשקול מחדש את הצעת צ'מברלין לגבי אוגנדה. בעקבות הפרעות התחיל הרצל לתכנן מהלך מדיני במספר ערוצים במקביל: מלבד הצ'ארטר הבריטי לגבי אוגנדה, ביקש להשיג זיכיונות דומים גם בקונגו מממשלת בלגיה, במוזמביק מפורטוגל ובטריפולי מאיטליה. הוא חשב על יצירת שש מושבות יהודיות באפריקה ובמקומות אחרים, שתשמשנה בסיסים לאומיים ליישוב ארץ ישראל בשלב מאוחר יותר. הוא הגדיר זאת: "אנגליה במהופך ובזעיר־אנפין", כלומר: בעוד שבאימפריות הקולוניאליות מייסדת ארץ האם את המושבות – אצל היהודים יוקמו קודם המושבות ורק לאחר מכן תקום מדינת האם שלהן במולדת. במאי 1903 הודיע צ'מברלין לליאופולד גרינברג כי ממשלת בריטניה מסכימה להחכיר לציונים אזור גדול מאוד, לא באוגנדה ממש, אלא בעמק המפריד בין שבט מאו לשבט קיקויו (כיום בקניה), שם יוכלו לכונן "ממשל עצמי" באזור שיוכל לקלוט מיליון מתיישבים. ביוני הוזמנה טיוטת צ'ארטר לאוגנדה, לקראת הקונגרס הציוני הקרוב. שם המושבה המיועדת היה "New Palestine" ("ארץ ישראל החדשה"). נורדאו הזהיר את הרצל מפני ההתנגדות לתוכנית אוגנדה בקרב יהודי מזרח אירופה, וב-13 ביולי השיב לו הרצל: "והרי זאת תכליתה של מנהיגות, להראות את הדרך, אשר אפילו על ידי מה שנראה כסטייה, תוליך את עמנו אל המטרה. גם משה רבנו כזה היה גורלו". במקביל, חידש הרצל את מגעיו עם הסולטאן העות'מאני במטרה לדון על הצעתו לגבי ארם נהריים, וב-4 ביוני כתב על כך למזכירו, איזט ביי. באותו זמן גם הוצע להרצל שטח אדמה גדול בעמק יזרעאל על ידי בעל קרקעות ערבי גדול ממשפחת סורסוק, אולם הרצל חשש לקנות אותו ללא ערבויות בינלאומיות. בנוסף לכך, השטח לא היה ריק מתושבים והרצל הסתייג מההשלכות של קנייה כזו ואמר: "אי־אפשר לנו לנשל את הפלאחים העניים הללו".
פנייתו לרוסיה הצארית (1903).
ב-20 ביולי 1903, כחודש לפני הקונגרס הציוני השישי, שלח הרצל לידידו הבריטי ג'וזף קאוון מכתב מקודד שעסק בעיתונאי הבריטי האנטישמי ארנולד וייט. וייט, שחשש מהגירת יהודים מרוסיה לאנגליה, פנה עוד בסוף המאה ה-19 לצאר הרוסי והציע לו ליישב יהודים בארגנטינה הרצל הציע במכתבו שווייט יפנה שוב לרוסיה ויציע לה לאפשר התיישבות יהודית במרוקו. אולם הצעה זו לא יצאה אל הפועל.
במקביל לערוצים אלו, החליט הרצל לפנות גם ישירות לרוסיה. הוא רצה שתפעיל לחץ דיפלומטי על הממשלה העות'מאנית, שתרשה אוטונומיה יהודית בארץ ישראל, וכך תוכל רוסיה להיפטר מהאוכלוסייה היהודית שלה. פנייתו הראשונה לשר הפנים ויאצ'סלב פלבה וליועץ הצאר קונסטנטין פובדונוסצב לא נענתה. בקשתה של ברטה פון זוטנר מהצאר שייפגש עם הרצל נתקלה בסירוב. הרצל ביקש את עזרתה של אצילה פולנייה המתגוררת בסנקט פטרבורג ומיודדת עם פלבה. הפעם השיב פלבה שישמח לפגוש את הרצל והוא בהחלט מעוניין לארגן הגירת יהודים מרוסיה, "בתנאי שלא יחזרו". ב-5 באוגוסט יצא הרצל לרוסיה. כיהודי, נאלץ קודם לבקש היתר מיוחד לביקורו מהמחלקה לדתות "זרות" ברוסיה. אף על פי שהסתיר את דבר הנסיעה מרוב חבריו, קיבלו אותו ציונים נלהבים בתחנות רכבת רבות. היחיד שהתלווה אליו במסעו היה ד"ר ניסן כצנלסון, מראשי הציונים ברוסיה. ב-8 באוגוסט התקבל אצל פלבה והשניים שוחחו בצרפתית. פלבה אמר כי הוא מעוניין "להגיע לידי הבנה" עם הרצל, והרצל הבין מכך שפלבה מעוניין מאוד למנוע דיון על פרעות קישינב בקונגרס הציוני הקרוב. פלבה הסביר כי היהודים הם "גוף זר" במדינה, שחלה עליהם מכסה בכניסה להשכלה גבוהה, אחרת "לא יישארו משרות בשביל נוצרים", ושהם מהווים מחצית מהמהפכנים. הרצל הבטיח שאם יקבל את ארץ ישראל, זרימת יהודים אל הסוציאליסטים תחדל. פלבה הכריז כי הוא תומך נלהב בציונות ושאל במה יוכל לעזור. הרצל הציג שלוש בקשות מממשלת רוסיה: שתלחץ על הסולטאן להעניק לציונים צ'ארטר להתיישבות בארץ ישראל, מלבד המקומות הקדושים; שתתמוך כספית בהגירת יהודים לארץ ישראל, כאשר הכספים יבואו מהמסים שמשלמים נתיני רוסיה היהודים; ושתרשה את ארגונן ופעולתן של אגודות ציוניות. פלבה הסכים מיד לשלוש הדרישות וביקש מהרצל לכתוב תזכיר לקראת פגישתם הבאה. לאחר שהרצל עזב, אמר פלבה למכרו כי לא ידע "שמצויים יהודים שאינם זוחלים".
לאחר מכן ביקר הרצל אצל שר הכספים, הרוזן סרגיי ויטה, שפתח בנאום אנטישמי: "היהודים מספקים די סיבות לאיבה. יש בהם שחצנות אופיינית, אולם רובם עניים, ומפני שהם עניים הם מלוכלכים ועושים רושם דוחה. הם גם עוסקים בכל מיני עיסוקים מכוערים, כרועי-זונות ומלווים בריבית. ומשום כך קשה כל-כך להגן עליהם. ובכל זאת, הנני ידיד היהודים". ויטה סיפר להרצל שאמר לצאר המנוח אלכסנדר השלישי: "אילו היה אפשר להטביע שישה או שבעה מיליונים היהודים בים השחור, הייתי מצדד בכך בהחלט. אבל אם אי-אפשר הדבר, יש להניח להם לחיות". הרצל הציג את תוכניתו ליציאת היהודים, וביקש מוויטה שהממשלה תנקוט "צעדים מסוימים של עידוד", וויטה השיב: "אך הרי מעודדים את היהודים להגירה, למשל בבעיטות באחוריים". הרצל השיב כי סוג העידוד הזה "ידוע ומוכר", ואין זה הסוג שעליו הוא מדבר. הוא חזר על שלוש הבקשות שהציג בפני פלבה, וביקש גם הסרה מיידית של האיסור על רכישת מניות הבנק הציוני. ויטה הבטיח לעזור.