בשנת 1895 החל הרצל בניסיונותיו לשכנע יהודים עשירים לתמוך בתנועה הציונית הממוסדת בהנהגתו. בחודש מאי פנה לנדבן היהודי ואחד מעשירי העולם, הברון הירש, במטרה שיעזור לממן את יציאת יהודי אירופה. הרצל הכין תזכיר בן 22 עמודים, באמצעותו הציג את תוכניתו. אולם הפגישה הייתה כישלון. הרצל היה מתוח ותוקפני וללא ידיעה מספקת על פעולותיו של הירש. הוא תקף את ניסוייו בארגנטינה, שבמושבות שהקים בה באמצעות יק"א ישבו אז כ-6,000 יהודים בלבד, וטען כי הוא "מגדל פושטי־יד". הרצל טען בפניו שלפני הגירת היהודים יש לחולל בעם שינוי במקומות מושבו: "יש לעשותו אמיץ־לב, נכון למלחמה, חרוץ בעבודה ובעל מידות טובות". הוא טען כי "יש להשפיע על ההמונים על ידי פנייה אל הדמיון, בסמלים כבירים... אומות מושפעות על ידי דגלים, עיטורים, שירים". הירש טען אמנם כי "הגירה היא הפתרון היחיד" וש"יש די ארצות העומדות למכירה", אולם כינה את רעיונותיו של הרצל "המצאות דמיוניות". פגישתם הסתיימה מבלי שהרצל הספיק להציג בפני הירש את תוכניתו לכינוס קונגרס יהודי בינלאומי שידון בכינון מדינה יהודית. בשובו הביתה, מיהר הרצל להתחיל בכתיבת יומנו המדיני, תחת הכותרת "שאלת היהודים", שהוקדש כולו לשאלה זו בלבד, ללא התייחסות לחייו המשפחתיים או לעבודתו כעיתונאי. היומן מתאפיין בגילוי־לב אנושי, הכולל את חלומותיו, שאיפותיו והפלגות־דמיונו של הרצל ללא שמץ מבוכה. לאחר פגישתו עם הירש, כתב לו הרצל מכתב בו הסביר כי יש בידו תוכנית ודרוש לה הרבה כסף לשם יצירת "אמצעי תעבורה, צורכי־מזון להמונים" וכן "בנין ערים ושכונות חדשות", אולם קודם לכן דרושה "תעמולה עצומה... תמונות, שירים... דגל... את הפוליטיקה של עם שלם – בייחוד עם המפוזר בכל העולם – אפשר לנהל רק באמצעות דברים אשר אין להם שיעור, דברים המרחפים באויר". הרצל כתב כי יציאת היהודים "היא למעשה מבצע עצום של תעבורה, שאין לו תקדים בעולם המודרני" ושלצורך כך בכוונתו לערוך מִלווה יהודי לאומי וביקש מהירש 50 מיליון מארק. נימת המכתב הייתה יהירה. לאחר מכן התחרט הרצל על מכתבו המתנשא לברון הירש.
"נאום אל הרוטשילדים", 1895.
הרצל החליט לפנות למשפחת רוטשילד בבקשה לסייע בהקמת "חברת היהודים", שתהיה אחראית על המשא ומתן על קניית ארץ, תארגן את ההעברה ההמונית של המהגרים, ותהווה מעין גרעין של ממשלה חדשה. משפחת רוטשילד אמורה הייתה לגייס למטרה זו את יוקרתה ואת קשריה בעולם, ובעיקר את כספה: תמורת מיליארד פרנקים שתתרום למלווה הלאומי, יהיה אחד מבניה הראשון שיעמוד בראש הרפובליקה החדשה. ביוני 1895 חיבר הרצל תזכיר ארוך בשם "נאום אל הרוטשילדים", אותו התכוון להשמיע בכינוס של משפחת רוטשילד. בתזכיר ניבא הרצל כי הונם של בני משפחת רוטשילד יוחרם במוקדם או במאוחר, וגם הם, כמו כל היהודים, יגורשו מכמה ארצות: "ובארצות שם נבקש מקלט, יהרגו אותנו". לטענתו בתזכיר, ארץ ישראל אינה מתאימה כטריטוריה החדשה, משום שהיא קרובה מדי לאירופה ויש לבודד את המדינה החדשה מן הסערות החברתיות והצבאיות של היבשת. מלבד זאת, רוב היהודים כבר התרגלו לאקלים שונה מזה של המזרח. ארץ הבחירה תיבחר על ידי ועדה של גאוגרפים ואנשי מדעי החברה. התזכיר דיבר על אופייה של המערכת הכלכלית ופירט את סדרי הממשל, הצבא, העבודה והתרבות. התזכיר קבע כי המדינה החדשה לא תהיה תאוקרטיה, מכיוון ש"הדת מאחדת אותנו, המדע עושה אותנו בני־חורין"; וכי שפתה לא תהיה עברית, שכן כמה יהודים מסוגלים לקנות כרטיס־רכבת בלשון זו? לכן השפה העיקרית תהיה גרמנית, בשל קרבתה ליידיש. למרות הפיכתו ליהודי לאומי, עדיין ראה עצמו הרצל גרמני: "הנני יהודי גרמני מהונגריה, ולעולם לא אוכל להיות אלא גרמני".
בינתיים כתב הרצל מכתב אל אוטו פון ביסמרק, קנצלר גרמניה לשעבר, בו סיפר לו על תוכניתו. לאחר מכן כתב לאלברט פון רוטשילד , ראש הענף הווינאי של המשפחה. הוא הודיע לו על כוונתו לפנות אל הקיסר הגרמני וביקש ממנו לשמש כעד על כוונותיו הטובות. גם ביסמרק וגם רוטשילד לא השיבו לו. ביסמרק אמר לאחד ממכריו כי תוכניתו של הרצל היא סכנה הן לגרמניה והן ליהודים.
באמצע יולי 1895 שוב פרצו בווינה מהומות אנטישמיות. ב-27 ביולי 1895 עזב הרצל את פריז והצטרף אל משפחתו בעיירת הקיט אאוסזֶה שבאוסטריה עילית. קירותיה של בקתת הרחצה שעל חוף האגם היו מכוסים כתובות אנטישמיות, אך לצידן היו גם תגובותיהם של נערים יהודים. הרצל העתיק אחת מהן לפנקסו: "אלוהים, שלח את משה אלינו ויאחז בידם של כל יהודינו ויחזירם לארץ־הבחירה". ב-17 באוגוסט הגיע הרצל למינכן, שם נפגש עם ד"ר מוריץ גידֶמן, הרב הראשי של וינה, ועם הנדבן הברלינאי היינריך מאיר-כהן, וקרא בפניהם את כתב היד של "נאום אל הרוטשילדים". לאחר ששמע את דבריו, אמר גידמן להרצל: "אתה מזכיר לי את משה!". שני האישים יעצו לו שלא "לבזבז" את הנאום על משפחת רוטשילד. גידמן יעץ לו "להביא את הרעיון אל העם, בצורת רומן", שעשוי להוביל ליצירת תנועת המונים גדולה.
שובו לווינה, 1895–1896.
בחירת לואגר לראשות העיר, 1895.
בספטמבר 1895, לאחר היעדרות של חמש שנים, חזר הרצל לווינה והחל במשרתו החדשה כעורך הספרותי של "נויה פרייה פרסה". מספר ימים לאחר הגעתו, זכו האנטישמים בראשות קרל לואגר לרוב במועצת העיר, ולואגר עצמו נבחר לראשות העיר. לואגר כבר נבחר עוד קודם לכן, אלא שגם אז וגם עכשיו, סירב הקיסר פרנץ יוזף, שהיה בעל דעות ליברליות והומניסטיות, לאשר את מינויו לראש העיר. למרות זאת, היה לואגר נערץ על ההמונים. ביום הבחירות יצא הרצל אל הרחובות, שם נוכח עד כמה "עמוקים שורשיה של האנטישמיות בליבות האנשים האלה". בניגוד לרוב יהודי וינה, הצטער הרצל על סירובו של הקיסר לאשר את הבחירה, משום שסבר כי השעיית לואגר רק הגבירה את השנאה ובסופו של דבר יאלץ הקיסר להיכנע להמונים. בנובמבר אמר לרוזן באדֶני, ראש הממשלה הקיסרי, כי מוטב לקיסר לאשר את הבחירה.
בחירתו של לואגר העלתה אצל הרצל את החשש מפני עלייתה של אנטישמיות תוקפנית דווקא עם הרחבת זכות הבחירה. הוא ראה בכך סימן אפשרי להתערערות יציבותה של האימפריה האוסטרו-הונגרית, שהייתה בעיניו ערובה להבטחת מעמד היהודים.
קונטרס פוליטי, 1895.
בתוך מספר שבועות מחזרתו לווינה, כבר התכתב הרצל עם יהודים בכל רחבי העולם שהתענינו בתוכניתו. בעקבות עצת אביו לפנות אל ההמונים, שכתב הרצל את "הנאום אל הרוטשילדים" לקונטרס פוליטי. הוא דרש משני עורכי ה"נויה פרייה פרסה", באכר ובנדיקט, לפרסם את תוכניתו בגיליון יום ראשון של העיתון, כאשר על עמוד השער תופיע הכותרת "הפתרון לשאלת היהודים, מאת ד"ר תיאודור הרצל". הרצל התכוון לפנות אל היהודים בדרישה לשאול שאלות ולהעיר הערות, ובכך לפתח ויכוח שיצור עניין בנושא. אולם בנדיקט חשש מתגובה אנטישמית וסירב לדרישתו של הרצל. לאחר מכן כתב הרצל ביומנו: "אני אהיה פרנל של היהודים". ב-11 בנובמבר 1895 יצא לפריז. באותו יום שוב התרחשו מעשי אלימות בווינה, משום שיום קודם לכן שוב סירב הקיסר לאשר את בחירתו של לואגר לראשות העירייה. בפריז נפגש הרצל לשלוש שיחות ממושכות עם הרב הראשי של צרפת, צדוק כהן. זו הייתה הפעם הראשונה שהרצל ביקש להיפגש עמו, אף על פי שהתגורר בפריז במשך ארבע שנים. כהן הביע את אהדתו לתוכניתו של הרצל והציג אותו בפני מספר אינטלקטואלים יהודים צרפתים. כאשר אחד מהם הדגיש בפני הרצל כי לאומיותו היא צרפתית, השיב לו הרצל: "מה? האם אין אתה ואני משתייכים לאותה אומה? מדוע נחרדת כשנבחר לואגר? מדוע סבלתי אני כשהואשם קפיטן דרייפוס בבגידה במולדת?". בפריז נפגש הרצל גם עם מקס נורדאו, שהיה אז הוגה דעות חשוב ומפורסם באירופה. נורדאו נסחף מיד אחר רעיונו. למחרת יצא ללונדון וביקר אצל ישראל זנגוויל, שהיה סופר יהודי-אנגלי ידוע. זנגוויל הסכים עם תוכניתו של הרצל וטען כי הוא תומך במדינה יהודית מנקודת השקפה גזעית: "הננו גזע, לכן הננו אומה". הרצל חלק על השקפה זו וטען: "הננו יחידה היסטורית, אומה רבת ניגודים אנתרופולוגיים. אבל גם בכך די למדינה יהודית. אין אומה בעלת אחידות גזעית". באמצעות זנגוויל, הכיר הרצל מספר אישים מרכזיים בקהילה היהודית של לונדון. אחד מהם היה סר סמואל מונטגיו, בנקאי חשוב וחבר פרלמנט, שנענה לתוכניתו של הרצל בהתלהבות, אך התנה את תמיכתו הפוליטית והכספית בכך שהמדינה היהודית תקום אך ורק בארץ ישראל, וטען כי ניתן לקנות אותה תמורת שני מיליון לירות שטרלינג. בנאומו במועדון המכבים, השמיע הרצל לראשונה את תוכניתו בפומבי. הנאספים קמו על רגליהם והריעו לו ומיד בחרו בו לחבר-כבוד של המועדון. עם שובו לווינה, החל לעבוד על הקונטרס. הוא ניסח מחדש והרחיב את "הנאום אל הרוטשילדים" למאמר יותר עובדתי ופחות מליצי, והשתדל להימנע מיצירת רושם של אגדה אוטופית או רומן פוליטי. סיפורים אוטופיים דמיוניים היו נפוצים בשנות ה-90 של המאה ה-19, והרצל חשש שישוו אותו לתיאודור הרצקה, שהיה עורך כלכלי של "נויה פרייה פרסה" וכתב ב-1890 את הרומן "ארץ החופש" (Freiland) – תוכנית למדינה אוטופית באפריקה המשוונית, שהעיתונות הפופולרית לעגה לו ולעלילותיו. הרצל סבר כי להבדיל מתוכניותיהם של בעלי האוטופיות הללו, מדינת היהודים תוקם בעזרת "כוח טבע" והוא "מצוקת היהודים". ב-24 בדצמבר הגיע הרב גידמן לבקרו. הרצל היה עסוק בהדלקת עץ חג המולד עבור ילדיו והרב מחה על כך שמנהג נוצרי זה מתקיים בביתו של האדם שרואה עצמו כגואל היהודים. הרצל הגיב על כך: "לא אניח שילחצו עלי. לדידי יקראו לו אילן־חנוכה".
הקונטרס "מדינת היהודים" (1896).