משפחת מוצרי ייסדה את "חברת מלונות ארץ ישראל" (Palestine Hotels Ltd) לצורך ההשקעה בהקמת המלון. בשנת 1929 החברה רכשה מהפטריארכיה היוונית-אורתודוקסית של ירושלים שטח גדול של כ-18 דונמים ברחוב שנקרא אז "רחוב יוליאן" (לימים רחוב המלך דוד). עלות רכישת השטח הייתה 31,000 לא"י - סכום עצום באותה עת. השטח שנרכש נבחר בזכות מיקומו הכלכלי-אסטרטגי, ובזכות הנוף הנשקף ממנו. השטח נמצא מול חומות העיר העתיקה ומגדל דוד, וכן למול הר ציון. קרבתו של המלון למגדל דוד ולקבר דוד העניקה את ההשראה לשם שנבחר עבורו - "King David"- "המלך דוד". השם נועד לשקף הדר מלכות, כמקובל במלונות הפאר של אירופה באותה תקופה, ובה בעת להיות יהודי וארץ-ישראלי. השטח נמצא מערבית לגיא בן הינום, בסמוך למרכז המסחרי בממילא ולשכונות היהודיות ימין משה ומחנה ישראל. כמה שנים לפני כן הוחל בבניית מרכז ימק"א ירושלים מעברו השני של הרחוב, ועם סיום בנייתו ניצבו שני המבנים המרשימים זה מול זה.
שנים ראשונות.
המלון נפתח לציבור ב-20 בדצמבר 1930. מנהלי המלון המצריים שאפו לשמור על רמה גבוהה בירושלים של אותה עת, שהייתה עיר פרובינציאלית ולא מפותחת. על מנת לשמור על רמה זו, הובאו מדי יום מצרכי מזון אל המלון ברכבת מקהיר. צוות המלון הובא מכל רחבי העולם. המלצרים הובאו ממצרים או מסודאן, צוות ההנהלה שנשכר היה שווייצרי והשפים שהובאו - איטלקים. המצב הפוליטי-כלכלי בארץ השתנה במהלך הבנייה. פרוץ מאורעות תרפ"ט ב-1929 מחד, והשפל הכלכלי הגדול מאידך, הביאו לירידה חדה במספר התיירים, הצליינים והעסקנים שהגיעו לארץ ישראל. רק כשנתיים לאחר פתיחתו, בשנת 1932, חלה התאוששות ועסקי המלון החלו לפרוח, ואף להביס את מלון פאלאס המתחרה שנבנה בסמוך בידי המועצה המוסלמית העליונה.
עם פרוץ המרד הערבי הגדול בשנת 1936 הואטה שוב תנועת התיירים לירושלים, ונפגעה הכנסת המלון. היחידים שהתארחו במלון באותה עת היו חברי ועדת פיל.
בשנת 1938 חכרו שלטונות המנדט הבריטי את האגף הדרומי של המלון, שהפך למקום מושבו של מינהל השלטון הבריטי. מאחר שתפוסת המלון באותה עת הייתה דלה, העבירה חכירה זו את מאזן המלון מהפסד לרווח.
לפני קום המדינה שימש המלון כאתר האירוח המרכזי במזרח התיכון. במלון התארחו מצביאים ומנהיגים בריטיים ובהם וינסטון צ'רצ'יל ולורד אדמונד אלנבי. כן התארחו בו מנהיגים אחרים, בהם היילה סלאסי, קיסר אתיופיה, לאחר שארצו נכבשה בידי איטליה, אלפונסו השלושה עשר, מלך ספרד לאחר הדחתו וגאורגיוס השני, מלך היוונים במהלך מלחמת העולם השנייה, עת הגיע למזרח התיכון לבקר את חיילי ארצו.
הפיצוץ במלון.
בבוקר יום 22 ביולי 1946, במהלך המרי העברי נגד הבריטים, חדרו למלון אנשי אצ"ל מחופשים לעובדי מטבח ערבים, והחדירו למסעדת לה רג'אנס שבקומת המרתף של האגף הדרומי כדי חלב גדולים שהכילו כ-350 ק"ג חומר נפץ. לאחר שעות אחדות, בשעה 12 בצהריים, הודיעו אנשי האצ"ל על פיצוץ קרוב של המלון. על פי אחת העדויות, ראש המינהל הבריטי, סר ג'ון שאו, הגיב על כך ב"לא באתי לכאן כדי לקבל פקודות מהיהודים", והורה שלא להעביר את ההודעה לעובדים הרבים שנותרו במשרדיהם. הוא הכחיש את הדברים וטען כי לא קיבל אזהרה כזו וגם אם היה מקבל, לא היה זמן לפנות את העובדים. בשעה 12:30 הרס פיצוץ אדיר את כל האגף הדרומי של המלון על כל קומותיו. בפיצוץ נהרגו 91 איש: 28 בריטים, 41 ערבים, 17 יהודים ו-5 מאורחי המלון, ועשרות נפצעו. במשך יומיים עמלו מהנדסי הצבא הבריטי המלכותי על חילוץ הגופות.
האגף שפוצץ לא שוקם, והצבא הבריטי העביר את משרדיו לחדרים אחרים במלון, ובפברואר 1947 הפך את המבנה לחלק מ"אזור ביטחון ב'" - שטח מבוצר המוקף שקי חול וגדרות תיל. רק אנשי מינהל בריטיים הורשו להתגורר ב-100 חדרי המלון הנותרים.
מלחמת העצמאות.
לאחר עזיבת הבריטים את ירושלים, ב-15 במאי 1948 הורד דגל היוניון ג'ק הבריטי מגג המלון.
המלון הנטוש והחרב הפך למפקדת נציגי ארגון הצלב האדום הבינלאומי, אולם מיקומו - על קו התפר בין העמדות הישראליות בשכונות משכנות שאננים וימין משה, לבין העמדות הערביות על חומת ירושלים, מול עמדות הלגיון הערבי הירדני - הביא לכך שמדי יום נורו על המלון עשרות כדורים ופגזים.
חיים הרצוג מתאר ביומנו את המלון במלחמת העצמאות:
אנשי הצלב האדום ניצלו את ההפוגה הראשונה ועברו לבניין ימק"א ירושלים הממוקם מאחורי מלון המלך דוד, ומוגן בשל כך מירי ישיר מהעיר העתיקה, ואנשי האו"ם החליטו לעשות שימוש במלון הנטוש כמפקדתם. על אף דגל האו"ם שהתנוסס על הבניין, הוא ספג פגיעות רבות נוספות עקב קרבתו לעמדות "ההגנה" בשכונת ימין משה ומשכנות שאננים. בשיאם של הקרבות אילצו הפגיעות הרבות את אנשי האו"ם לעזוב את מבנה המלון, וכוחות צה"ל השתלטו על הבניין והקימו בו עמדות אל מול חומת העיר העתיקה. בסיום הקרבות שורטט "הקו העירוני" במרכז גיא בן הינום - בין עמדות צה"ל שבמלון ועמדות הלגיון הערבי הירדני על חומות העיר העתיקה. המלון מצא עצמו מטרים ספורים מקו הגבול.
תקופת ירושלים החצויה.
עם סיום הקרבות חזר המלון לתפקד בניהולה של חברת מלונות ארץ-ישראל. החברה העדיפה שלא להשקיע בשיקום המלון, וניסתה לצמצם את הפסדיה משלהי תקופת המנדט ומתקופת מלחמת העצמאות באמצעות שימוש בחדרי המלון הקיימים, מבלי לשפצם.
במלון התארחו שגרירי מדינות שהגיעו לישראל והמלון דאג להניף את דגלי המדינות ששגריריהם שהו במלון. ב-1955, בעת ביקור או נו בישראל, הביקור הראשון של ראש מדינה זרה במדינת ישראל, לן או נו, ראש ממשלת בורמה במלון ופתח בכך מסורת לפיה לנים במלון ראשי מדינות המבקרים בישראל.
בעקבות המצב הביטחוני הייתה ירידה גדולה בתיירות לישראל בכלל ולירושלים בפרט, שפגעה בבתי המלון בירושלים. מלון המלך דוד, על 150 עובדיו, הגיע לתפוסה של כ-40–50 אורחים והחל במסע צמצום עובדים ובחיפוש אחר שווקים חדשים כמו פעילות כבית הבראה. ניסיון להביא את פקידי ההסתדרות לנפוש במלון כשל, אף על פי שהוצע מחיר זול, מחשש שהדבר ייחשב למנקר עיניים. צעד נוסף שנעשה כדי למשוך לקוחות היה הקמת אגף כשר, לאחר שבמשך שנים המלון לא הוכשר. בנובמבר 1956 נסגר המלון בגלל הפסדיו ועובדיו פוטרו. לאחר שניסיונות למצוא קונה למלון כשלו, הילטון למשל נמנעה לחכור את המלון בגלל לחץ ערבי, נפתח המלון מחדש על ידי בעליו הקודמים, לאחר שקיבל הנחות במיסים מהעירייה והממשלה.
בראשית 1958 רכשה משפחת פדרמן, בעלת רשת מלונות דן, את מחצית המניות של חברת מלונות א"י, בעלת המלון ויקותיאל פדרמן מונה ליו"ר מועצת המנהלים של החברה. אגפו הדרומי של המלון נותר הרוס, וקירותיו המזרחיים טרם שופצו מהפצצות מלחמת העצמאות. לאחר הרכישה החלו עבודות שיפוץ ושיקום המלון. האגף הדרומי שוקם על ידי הקבלן החיפאי חיים אלוני. עלות השיפוצים עלתה על 2 מיליון דולרים. השיפוצים כללו עבודות תשתית נרחבות ושינויים מבניים בכל קומות המלון וחדריו. עד לשיפוץ זה היה חדר אמבטיה אחד בכל קומה, ששימש את כל החדרים באותה קומה (למעט הסוויטות, שאורחיהן נהנו מחדר אמבטיה פרטי). במסגרת השיפוץ נבנו חדרי אמבטיה ושירותים בכל חדר, הוחלפו תנורי ה"ברנר" שהיו במטבח המלון מאז שנות ה-30, שכן ארובותיהם הפיצו עשן שחור עקב השימוש בסולר והכתימו את קירות המלון, והרדיאטורים הוחלפו במערכת חימום ומיזוג. במהלך השיפוץ הקפידו על שימור צביונו ועיצובו המקורי של המלון, על סגנונו המזרחי המיוחד. מיטות האפריון שהיו בחדרים משנות ה-30 הוחלפו בהעתקים זהים שנבנו על ידי אברהם קריניצי (לימים ראש עיריית רמת גן). רהיטי הלובי המקוריים שופצו ונותרו במקומם. בשנת 1961 הסתיים שיקומו של האגף הדרומי, אשר הוסיף 56 חדרים ל-100 חדרי המלון. בשנת 1963 שופץ גם המרתף בו הונח חומר הנפץ בעת הפיצוץ ובתחילת 1964 נפתחה מחדש מסעדת לה רג'נס.
המלון נחשב למועדף על ידי אנשי ממשלת ישראל, חברי הכנסת ואנשי הצבא. אורחיה הרשמיים של מדינת ישראל התגוררו במלון, ובו נערכו להם ארוחות רשמיות. באותה עת טרם נבנה משכן נשיאי ישראל, והמלון שימש, בין היתר, כאתר עבור נשיא מדינת ישראל לארח את אורחיו. בתקופה זו, עקב קרבת המלון לעמדות הלגיון הערבי (כ-1,000 מטרים), צלפו לעיתים חיילי הלגיון על חדרי המלון.
הגידול במספר חדרי המלון הביא למעשה לתפוסה נמוכה יותר בו, מאחר שתנועת התיירות הייתה דלילה למדי בירושלים באותה עת. העיר, שהייתה עיר ספר מבודדת, הציגה מספר מועט של אתרי תיירות (מרבית אתרי התיירות ההיסטוריים נותרו בעיר המזרחית ובעיר העתיקה). מרבית התיירים שהגיעו אל העיר היו יהודים שבאו לצפות בעיר העתיקה מאחת מתצפיות שהוקמו לצורך זה, ושבו לתל אביב עוד באותו היום. רשת דן ניסתה להגדיל את תפוסת המלון בכך שדרשה מתיירים שרצו ללון במלון דן תל אביב, שנחשב באותה עת לטוב ולמבוקש במלונות מדינת ישראל, שילונו לילה אחד גם בירושלים.
המיתון של שנות ה-60 פגע אף יותר בכלכלה הישראלית ובתנועת התיירות. הנהלת המלון החליטה לנצל את המחירים הזולים בשל המיתון ואת העובדה שלא הגיעו תיירים לירושלים, לבצע שיפוץ נוסף במלון ולהוסיף לו שתי קומות, שנחנכו ביולי 1969. מיד לאחר מכן נקבע עם שר התיירות שייבנה ליד המלון מגדל בן 22 קומות עם עוד כ-200 חדרים, אולם התוכנית בוטלה בגלל טענות לפגיעה בנוף.
הרחבת המלון.