בשנת 1896 פרסם הרצל קונטרס בן 68 עמודים, וקרא לו "מדינת היהודים: ניסיון לפתרון מודרני של שאלת היהודים".
הרצל הציע בספרו פתרון מעשי לבעיית היהודים ולחוסר יכולתה של אירופה לפותרה. הוא הדגיש בו כי יש להשיג הכרה בינלאומית ומשפטית בזכויות העם היהודי למדינה משלו, שיכולה לקום בארגנטינה או בארץ ישראל.
לא נמצא מוציא לאור בעל מוניטין שהסכים לפרסם את הספר, והרצל הוציאו לאור אצל מקס ברייטנשטיין, יהודי מתבולל שהיה בעליה של חנות ספרים קטנה בווינה. ב-17 בינואר 1896 פורסמה ב"ג'ואיש כרוניקל" של לונדון תמצית קצרה של הספר. עורכי העיתון "נויה פרייה פרסה" נתקפו בהלה משום שהרצל זוהה ב"כרוניקל" כעורך האחראי של העיתון הווינאי. בעקבות זאת לחצו על הרצל לעכב את הדפסת הספר, אך הרצל סירב להמתין. הספר זכה לפרסום רב לאחר הוצאתו, אולם גם ובעיקר ללעג ולביקורת שלילית. מיעוט הקוראים האוהדים היו בעיקר יהודים רוסים שהתגוררו בגרמניה ובאוסטריה. עיתוני וינה תקפו את הרצל ואת הקונטרס שלו. הסופר היהודי שטפן צוויג כתב כי "שום אדם בווינה לא הושם ללעג כהרצל". עיתונו של הרצל שמר על שתיקה. בנדיקט הפר את הבטחתו המוקדמת להרצל לפרסם בעיתון ביקורת על הספר והוציא פקודה האוסרת להזכיר אותו ואת הנושא בו הוא עוסק בטורי העיתון. לאחר פרסום הקונטרס, הפסיק פתאום הרב הראשי גידֶמן את תמיכתו בהרצל. העיתונות הגרמנית-יהודית תקפה את הרצל כדמגוג חסר אחריות וכשקרן. נציגיהן של כ-500 קהילות יהודיות באוסטריה-הונגריה הגישו עצומה לקיסר וביקשו לאסור בחוק את הציונות כתנועה אנטי-דתית.
ההנהגה היהודית בהונגריה חששה מכך שהממשל יקבל את הטיעונים הציוניים ויכיר בתנועה, ולראשונה מזה חצי יובל התאחדו האורתודוקסים והנאולוגים בהצהרת גינוי משותפת. הרב אריה ליפשיץ, ראש לשכת היראים, כתב: "המגיארים בני דת משה חפצים לפרוח כאן, בביתם; אין להם כל כוונה להקים מדינה יהודית בפלשתינה".
עם זאת, בווינה תמכו בהרצל אגודות הסטודנטים היהודיות באוניברסיטה, שהרצל עצמו התעלם מהן כשהיה סטודנט. הרצל גם הופתע לגלות כי ישנם ציונים ותיקים, רובם יוצאי מזרח אירופה, שייסדו כבר מעין תנועה ציונית. רק עתה קרא הרצל לראשונה את ספרו של פינסקר "אוטואמנציפציה!", והופתע מהדמיון לספרו, הן בניתוח הבעיה והן בפתרון המוצע לה. קריאתו של הרצל הדהדה בקרב יהודי מזרח אירופה והופעתו עוררה בהם התלהבות. הוא הוצף במכתבי תמיכה ממקומות שונים באירופה, בעיקר ממזרח אירופה. באספת המונים בסופיה שבבולגריה, הכריזו עליו כמשיח. "מדינת היהודים" תורגם למספר שפות. באמצע מרץ 1896 התגברה אצלו תחושת הפעמת. רופאו אבחן אצלו "מחלת־לב מחמת התרגשות" והמליץ על מנוחה ממושכת, אולם כעבור מספר ימים המשיך הרצל בעבודתו הקדחתנית. מרוב כתיבה, נתקף עווית בידו הימנית ובמשך מספר שבועות לא יכול היה לכתוב. מבקרים רבים החלו להגיע אל ביתו. במאי אותה שנה ביקר אותו דוד וולפסון, שמהר מאוד נעשה לראש עוזריו, ולאחר מכן גם מנחם אוסישקין. בפגישתם הראשונה של הרצל ואוסישקין הם לא פסקו להתווכח. כשעזב את ביתו של הרצל, העיר אוסישקין כי הרצל "אינו יודע ולא־כלום על היהודים. לכן הוא סבור שיש רק מכשולים חיצוניים לציונות".
הספר "מדינת היהודים" היווה בסיס לזרם הציונות המדינית, שתומכיה סברו, כי יש להשיג הכרה בינלאומית ומשפטית (צ'ארטר) בזכויות העם היהודי על ארץ ישראל לפני תחילת ההתיישבות בפועל – הסדר מדיני שיבטיח את זכותם של היהודים על הארץ, ורק אחרי השגת ערובות חוקיות וזכויות פוליטיות להתיישבות, ניתן יהיה להתחיל בהגירה (עלייה). דעתו זו של הרצל הייתה הפוכה מדעת "הציונות המעשית" של "חובבי ציון" בראשות אוסישקין, שפעלה באמצעות עלייה לארץ ישראל וקביעת עובדות התיישבותיות.
באפריל 1896 החליט הרצל לפנות שוב אל הברון הירש, אך היה זה מאוחר מדי. הירש נפטר באחוזתו בהונגריה. ביומנו כתב הרצל: "אבד ליהודים הירש, אך אני בא במקומו, וכשאסתלק אני, יהיה להם אחר. חייב להיות קו־עלייה".
פעילות מדינית, 1896–1904.
על מנת לממש את חזונו החל הרצל בפעילות דיפלומטית נרחבת, הן בקרב יהודים ובעיקר בין מנהיגי מדינות וארגונים, שמהם קיווה לקבל הצהרה בזכות הקמת מדינה ליהודים, הצהרה שהייתה צריכה לבוא לידי מימוש ב"צ'ארטר" (מסמך הכרה רשמי). הופעתו של הרצל העבירה את זירת הפעילות הלאומית אל מערב אירופה, כאשר מפעלם של חובבי ציון במזרחה ובמרכזה הועמד בסכנת קיום עם פרוץ הפולמוסים בשאלת היחס למסורת.
פנייתו לקיסר הגרמני ונסיעתו לקושטא, 1896.
הרצל ניסה למצוא דרכים להתקבל לריאיון אצל הקייזר הגרמני וילהלם השני, שעמד בראש הקיסרות הגרמנית. הוא תכנן לבקש מהקייזר להפעיל את השפעתו על הסולטאן העות'מאני עבדול חמיד השני לטובת הענקת צ'ארטר ליישב יהודים בארץ ישראל.
התנועה הציונית תתרום סכומי כסף לאימפריה העות'מאנית כעזרה בהתמודדות עם חובותיה של האימפריה למדינות אירופה, ובתמורה תוחכר ארץ ישראל ליהודים. בתיווכו של ויליאם הכלר, כומר השגרירות הבריטית בווינה, הצליח הרצל להיפגש באפריל 1896 עם פרידריך הראשון, הדוכס הגדול מבאדן, דודו של הקיסר. הרצל הצליח לשכנע את הארכידוכס בנחיצות פגישה מדינית. מבלי לספר זאת להרצל, המליץ עליו הדוכס לפני הקיסר.
עוד במרץ 1896 הכיר הרצל את פיליפ מיכאל דה נבלינסקי, אציל פולני בעל קשרים טובים בקושטא ומקורב לסולטאן העות'מאני, שהסכים, תמורת תשלום, להתלוות אליו בנסיעתו לקושטא. ב-15 ביוני יצאו השניים לדרך. בתחנת הביניים בסופיה, נערכה להרצל קבלת פנים על ידי המוני יהודים בולגרים, בה הוגש לו זר פרחים ונישאו נאומים. הרצל ונבלינסקי הגיעו לקושטא ב-17 ביוני, ובלחצו של נבלינסקי, שכר הרצל את הסוויטה המלכותית במלון אימפריאל, כדי להבליט את מעמדו כדובר של אומה שמאחוריו כוח כספי גדול. הרצל שוחח עם הווזיר הגדול (ראש הממשלה) חליל ריפאט פחה בארמון השער הנשגב. הוא הסביר לו את הצעתו והוסיף כי תמורת ויתורה של האימפריה העו'תמאנית על ארץ ישראל, מוכנים היהודים לשלם גם מס שנתי. הווזיר הבטיח לדווח על השיחה לסולטאן. הצעתו של הרצל לא הייתה יוצאת דופן במאה ה-19. מדינות נהגו להחליף, לקנות, למכור, לחכור ולהחכיר שטחים. רק 18 שנים קודם לכן חכרה אנגליה מידי העות'מאנים את קפריסין. הרצל העדיף עתה את ארץ ישראל על ארגנטינה, לא רק משום שהציונים הוותיקים רצו בה, אלא גם משום שחשב שניתן לבצע עסקה עם הטורקים. נבלינסקי עצמו נפגש עם הסולטאן ודיבר איתו על תוכניתו של הרצל. לדבריו, אמר לו הסולטאן: "אין אני יכול למכור שעל אדמה. לא שלי היא, כי אם של עמי... מוטב ליהודים שיחסכו להם את המיליארדים שלהם. אם ממלכתי תחולק, אולי יקבלו את ארץ ישראל חינם". בימים הבאים קיים הרצל פגישות נוספות עם הווזיר הגדול, ראשי משרד החוץ ומספר פחות. מהמט נור ביי, מזכ"ל משרד החוץ, הביע אהדה נלהבת לתוכנית של הרצל. גם איזט ביי, מזכירו של הסולטאן, היה אוהד ועודד את הרצל להמשיך במאמציו. לנבלינסקי אמר הסולטאן כי הוא מוכן לקבל את הרצל "בתור ידיד" לטורקיה, אולם קודם לכן עליו לעשות שירות למענו: להפעיל את השפעתו על העיתונות הבינלאומית "שתנהג יתר ידידות בטורקיה, בייחוד בעניין הארמנים" – שהרצל ישפיע על הארמנים הגולים שיחדלו לנהל תעמולה נגד טורקיה. הרצל הסכים לכך, אך הסולטאן לא קיבל אותו לראיון. ב-26 ביוני נזף הסולטאן בנבלינסקי ואמר לו כי "ארץ ישראל אינה עומדת למכירה". הוא שאל את נבלינסקי מדוע לא יכולים היהודים להתיישב במחוז אחר, וזה השיב לו כי "ארץ ישראל היא ערש־לידתם". הסולטאן טען בתגובה: "אבל ארץ ישראל היא גם ערש לידתן של דתות אחרות". הרצל חשש שאי קבלתו על ידי הסולטאן תגרום לתנועה הציונית לאבד תנופה. הוא נזקק להוכחה סמלית כלשהי של אהדה מצדו, ולכן ביקש מנבלינסקי שישיג לו לפחות עיטור טורקי גבוה. בינתיים סייר בארמונות הסולטאן כ"אורח רשמי" ושמונה שייטים במדים השיטו אותו בבוספורוס בסירת הסולטאן. מורה הדרך היה שלישו של הסולטאן, שהקפיד לפנות אל הרצל בפנייה "הוד מעלתך". בעקבות פנייתו של נבלינסקי, הוענק להרצל אות מסדר המג'ידיה מהמדרגה השלישית, אולם לדברי נבלינסקי, אמר לו הסולטאן כי התכוון להעניק להרצל את העיטור גם אם לא היה מבקש, ולא יכול היה לקבלו לראיון בביקור הזה משום שתוכניתו כבר אינה בגדר סוד.
ביקוריו בסופיה, בלונדון ובפריז.
על אף שלא התקבל על ידי הסולטאן, סבר הרצל כי נסיעתו לקושטא הייתה "הצלחה מזהירה". גם החרדה שהייתה תוקפת אותו בעומדו בפני רמי-מעלה החלה להתפוגג. ביומנו כתב: "רמי־המעלה כל מעלתם ביראת־הכבוד שאנחנו רוחשים להם". בדרכו חזרה עצר בסופיה, שם שוב נערכה לו קבלת פנים המונית. נסיעתו בחוצות העיר עוררה התרגשות ובבית הכנסת הוא הוצב על הבימה לפני ארון הקודש. ב-4 ביולי הגיע ללונדון כדי להציע לבנקאים יהודים להתלוות אליו למסעו הבא לטורקיה, אולם נתקל בהתנגדות מצד האצולה האנגלית-יהודית. ב-12 ביולי הופיע בפני קהל גדול במועדון הפועלים היהודים בוייטצ'אפל במזרח לונדון. על תחושתו בזמן שישב על הבמה אל מול הקהל המשולהב, כתב: "ראיתי והאזנתי להולדת אגדת אישיותי". בלונדון פנה אליו העיתונאי הציוני הצעיר יעקב דה האז, והרצל מינה אותו ל"מזכיר הכבוד" שלו בעיר.