ב-13 באוגוסט שוב נפגש עם פלבה, שהודיע לו כי הצאר אישר את שלוש בקשותיו. פלבה מסר להרצל כי הצאר נפגע מההתקפות נגדו בעיתונות הזרה ומן ההאשמות במעורבות בפרעות קישינב, וביקש למסור להרצל כי הוא מתייחס יפה לכל נתיניו. פלבה הודה כי מצב היהודים ברוסיה "אינו טוב ביותר", ומשום כך "רצוי לנו מאוד יסוד מדינה יהודית עצמאית שתהיה מסוגלת לקלוט כמה מיליוני יהודים... היינו רוצים לשמור לנו את מיטב האיטליגנציה... אבל היינו רוצים להיפטר ממחוסרי ההשכלה וממעוטי האמצעים". הרצל ביקש ממנו להקל על חייהם של היהודים ברוסיה ולהרחיב את זכות המגורים מחוץ לתחום המושב. פלבה הגיש לו מכתב שאושר על ידי הצאר ושיוכל לפרסמו, בו הבטיחה ממשלת רוסיה רשמית את תמיכתה בציונות, בתנאי שהציונים יעודדו יהודים ברוסיה לעקור למדינה היהודית בארץ ישראל. אך עם זאת, לא תורשה בממלכה הרוסית התארגנות יהודית על בסיס לאומי. במכתב ניתנה הבטחה לסייע כספית למהגרים היהודים, ולהתערב לטובת העניין הציוני בקושטא. הרצל לחץ שהצאר יתערב אישית אצל הסולטאן, ופלבה הבטיח לדבר על כך עם הצאר, אך לא הסכים לקבלת הרצל לראיון אצלו לפני הקונגרס הציוני הבא, ברמזו כי הוא מצפה ממנו לרסן את הביקורת הבינלאומית על ממשלת רוסיה. הרצל היה מרוצה מתוצאות מסעו לרוסיה. הוא הצליח להסיר את האיסור על ההתארגנות הציונית ואיסוף הכספים שלה, והצליח לקבל הבטחה להתערב בקושטא – הבטחה ראשונה מסוגה מצד מעצמה גדולה.
באותו ערב נאם הרצל בפני קבוצת פעילים ציוניים. רבים מהם זעמו על שיתוף הפעולה שלו עם פלבה ולא האמינו להבטחותיו של האחראי על פרעות קישינב. הרצל ביקש מהם לעסוק רק בארגון הציוני ולא בעידוד התרבות היהודית בתוך רוסיה, ולהימנע מפעילות סוציאליסטית לפני הקמת המדינה היהודית: "בארץ ישראל, בארץ שלנו, לא יהיה פסול במפלגה סוציאליסטית קיצונית... אז אקבע את יחסי שלי כלפיה... אולם עכשיו, במצבנו הנוכחי, מוקדם מדי לעסוק בעניינים כאלה. הם טפלים לעיקר. הציונות תובעת מעורבות גמורה, לא חלקית".
ביומו האחרון של הרצל בסנקט פטרבורג, הזהירו אותו מנהיגים מקומיים מהתנקשות בחייו והפצירו בו שלא להתעכב בשום מקום בדרכו חזרה לאוסטריה. אולם הרצל רצה לראות במו עיניו את החיים היהודיים במזרח אירופה וב-16 באוגוסט הגיע לווילנה. בתחנת הרכבת נערכה לו קבלת פנים נלהבת וסוערת. המשטרה פיזרה את ההמון באלות, אולם ההמון חזר והסתער בקריאות "הרצל, הרצל!" ו"יחי המלך!". בתוך ההמון שהצטופף ברחובות, נסע הרצל מוקף שוטרים וסוכני משטרה בלבוש אזרחי. המשטרה רצתה למנוע הפגנות נוספות ולכן ציוותה עליו שלא לצאת מבית המלון. כל האסיפות הפומביות לכבודו בוטלו, אך הרצל בכל זאת ביקר במשרד הקטן של הקהילה היהודית. רב הקהילה הגיש לו ספר תורה עתיק ואמר לו בהתרגשות: "אתה הגדול בבני עמנו". כל הנוכחים פרצו בבכי וגם הרצל התרגש מאוד. בשעה 1:00 בלילה, יצא מן המלון לתחנת הרכבת. המונים הריעו לו בסמטאות בגשם השוטף. קוזאקים על סוסים הסתערו על ההמון הצפוף ליד תחנת הרכבת. הם הצליפו בו בשוטיהם, הכו אותו ברוביהם ורמסו אותו עם סוסיהם. צעקות המוכים התערבבו בקריאות "יחי הרצל!". הרצל המזועזע קרא: "מדוע מכים את האנשים האלה? איזו פראות!". לפרנסי הקהילה שהמתינו לו על הרציף, אמר דברי עידוד: "רבותי, אל תתיאשו! יבואו ימים טובים יותר! לשם כך אנחנו פועלים!".
בזמן ששהה בווילנה, קיבל הרצל מברק מליאופולד גרינברג בלונדון, שהודיע לו כי הבריטים הציעו רשמית לכונן מושבה יהודית באפריקה המזרחית. בדרכו חזרה ברכבת לגרמניה, הגיע הרצל להחלטה לקראת פתיחת הקונגרס הציוני כעבור שישה ימים בלבד: מסעו לרוסיה הבהיר לו כי אף על פי שאוגנדה אינה ארץ ישראל, זו עת להציל את היהודים ואסור לאבד זמן. הוא התעכב יום אחד בעיר הנופש ההררית אלטאוסזה , שם בילו אשתו וילדיו בקיץ, ולמחרת בבוקר המשיך לקונגרס בבזל בלוויית אמו.
פולמוס אוגנדה בקונגרס הציוני השישי, 1903.
ב-23 באוגוסט 1903, התכנס הקונגרס הציוני השישי בבזל. הצירים זועזעו לנוכח השינוי שחל במראהו של הרצל, שנראה עתה עייף, חולה, קמטים בפניו וקומתו שפופה. לפני פתיחת הקונגרס כינס את הוועד הפועל לישיבה מוקדמת, שבה דיווח לחבריו על המשא ומתן שניהל עם ממשלת רוסיה. החברים הרוסים זועזעו לשמוע שהרצל לחץ את ידו של האחראי לרצח יהודי קישינב, פלבה, וזועזעו עוד יותר כשדיווח על "תוכנית אוגנדה" הבריטית. למחרת בבוקר התקבל בקונגרס בתשואות סוערות ונאם את נאום הפתיחה. הוא סקר בנאומו את האסונות האחרונים ואת החמרת מצב היהודים, ואמר: "נציל־נא את אלה שעוד ניתן להצילם". הוא דיווח על כישלון המשא ומתן עם העות'מאנים ועל כישלון המשא ומתן עם הבריטים בנושא סיני, והעלה לסדר היום של הקונגרס את ההצעה הבריטית בנוגע לאוטונומיה באוגנדה. הוא הדגיש כי הממשלה הבריטית יודעת כי מטרתה של הציונות היא שיבה לארץ ישראל ושאוגנדה תשמש "אתר ארעי להתיישבות על בסיס לאומי". הוא דרש מהקונגרס לקבל את ההצעה ונענה בסערת תשואות. אלא שתהום נפערה בין הסיעות, שפתחו בהתייעצויות במהלך הנאומים. בישיבה הסוערת של הסיעה הרוסית תקף הסטודנט הצעיר חיים ויצמן את הרצל בחריפות, וטען כי הממשלה הבריטית עתידה להציע "הצעה טובה יותר". כמה ממתנגדי תוכנית אוגנדה אף הכריזו על שביתת רעב. על אף שנורדאו לא תמך בתוכנית אוגנדה, הוא הגן על הרצל ואמר כי אוגנדה תשמש "מקלט לילה" לנרדפים. נוכח ההתנגדות הקשה והאיום בפילוג, הועמדה להצבעה רק החלטה מתונה מאוד – שיגור של משלחת מומחים לאזור המוצע באפריקה המזרחית.
הרצל ראה חשיבות בהצעה הבריטית, מפני שהייתה בה הכרה בריטית בתנועה הציונית ומחויבות של המעצמה העולמית לפתרון הבעיה היהודית. לעומתו, אישים כמו מנחם אוסישקין ואחרים מציוני רוסיה, בהם חיים ויצמן, טענו שהתמיכה בהצעה לשליחת משלחת החקר היא הצבעה נגד ארץ ישראל, שרק בה יכולה לקום מדינה יהודית. כפשרה בין הרצל למתנגדיו, הוחלט שהמימון למשלחת לא יהיה מהכספים הציוניים של אוצר התיישבות היהודים או הקרן הקיימת לישראל.
למרות הוויכוח אושרה ההצעה בסופו של דבר ברוב גדול. פרצה סערה ותוך איום בפרישה, עזבו החברים הרוסים בוועד הפועל, "אומרי הלאו", את מקומותיהם על הבמה ופרשו בהפגנתיות מהאולם יחד עם תומכיהם. רבים מהם בכו. הם התכנסו לישיבה סגורה באולם אחר, שנמשכה עד מאוחר בלילה, לאחר נעילת המליאה. הרצל שמע על הישיבה ההפגנתית וחזר מבית המלון אל הקונגרס. הוא דפק על הדלת הנעולה וביקש להיכנס. אחד הנוכחים בחדר צעק לעברו: "בוגד". נערכה הצבעה והוחלט להניח לו להיכנס. הוא ניגש לדוכן הנואמים וניסה לשכנע את המתנגדים. הוא ניסה להסביר להם את החשיבות בהכרה הבריטית ושדחיית ההצעה הבריטית כלאחר יד תפגע בתנועה הציונית. בשעה 2:00 בלילה החליטו המשתתפים לחזור למקומותיהם בישיבת הבוקר של הקונגרס. נאום הנעילה של הרצל היה הנאום האחרון שנשא בחייו בקונגרס כלשהו. הוא חזר בו על ההצעה הבריטית והדגיש שוב כי תוכנית אוגנדה היא פתרון ארעי. הוא סיים את נאומו בשבועה. הוא הרים את יד ימינו וקרא בעברית: .
לאחר הקונגרס חזר הרצל אל משפחתו באלטאוסזה. אשתו, ז'ולי, חלתה קשה בדלקת המעי העיוור שהוחמרה בשל דלקת ריאות, וחלק מהזמן הייתה מחוסרת הכרה. הרצל עצמו עבר התקף לב נוסף וסבל מעוויתות ברגליו. אך בעוד הוא מטפל באשתו החולה, החל לשלוח מכתבים לכל העולם. ב-5 בספטמבר שלח לפלבה דין וחשבון מפורט של הקונגרס, המוכיח כי יהודי רוסיה מוכנים להגר רק לארץ ישראל, ולכן יש להפעיל לחץ על הסולטאן. אלא שבאותו יום כתב לליאופולד גרינברג בלונדון כי עליו לעשות "מאמץ אינטנסיבי (אך סודי) להשיג במהירות את הצ'ארטר לאפריקה המזרחית". ב-11 בספטמבר אף כתב אל אוילנבורג בניסיון נוסף להשיג את תמיכת הקיסר הגרמני. ב-13 בספטמבר כתב אל ראש ממשלת אוסטריה, קרבר, וביקש ממנו "את תמיכת הממשלה של מולדתי". אף על פי שקיבל תשובות חמקניות, לא התייאש ושלח את קולונל אלברט גולדסמיד לדבר עם מלך אנגליה, ואת הפרקליט היהודי האיטלקי פליצ'ה ראונה לדבר עם האפיפיור. באוקטובר חזר למשרתו בווינה. ב-6 באוקטובר כתב פלבה להרצל כי שר החוץ, הרוזן ולדימיר לאמסדורף , יורה לשגריר בקושטא להודיע לממשלה העות'מאנית שממשלת רוסיה רוחשת יחס אוהד לתוכנית הציונית "ליישב את בני דתם בארץ ישראל", ושהיענות חיובית מצדה לבקשה הציונית, תגביר את קשרי הידידות בין שתי האימפריות. על פי הצעת פלבה, פנה הרצל לשגריר הרוסי בקושטא, אולם זה לא מיהר לבצע את ההוראות שקיבל.
לאחר הקונגרס הציוני השישי, כינס מנחם אוסישקין מועצה בחרקוב, שכללה, מלבדו, עוד שמונה מראשי המתנגדים ל"תוכנית אוגנדה". המועצה החליטה להגיש להרצל אולטימטום: ביטול תוכנית אוגנדה או פילוג התנועה הציונית. ההחלטה הייתה חשאית ונשלחה משלחת לווינה להציג את האולטימטום להרצל. אולם הרצל שמע על ההחלטה, ועם שוך הסערה בתנועה הציונית, שלח ב-12 בדצמבר מכתב פומבי אל סר פראנסיס מונטיפיורי, בו כתב כי התנגדות המתיישבים האנגלים באפריקה המזרחית להתיישבות יהודית שם, הפכה את תוכנית אוגנדה ל"בלתי-מעשית". ב-5 בינואר 1904 הגיעו לווינה שני נציגים מחרקוב. הרצל הסכים לקבלם, אך כיחידים ולא כמשלחת, וסירב לקבל "אולטימטום". הוא האשים אותם בחוסר נאמנות ובבגידה, והשניים יצאו מהפגישה נזופים.
פנייתו אל האפיפיור ופגישתו עם מלך איטליה (ינואר 1904).