דוד שאלתיאל נולד בהמבורג שבגרמניה, בשנת 1903. מצד אביו היה נצר למשפחה ספרדית מיוחסת, שנדדה מפורטוגל לאנגליה, ומשם להולנד, והשתקעה בגרמניה. שאלתיאל היה גאה בתואר ס"ט (ספרדי טהור), אף שאמו הייתה בת למשפחה אשכנזית, אף היא מיוחסת ואמידה. בגיל צעיר מאוד מרד באביו, שהיה דתי-קיצוני, ובגיל חמש-עשרה העמיד את אלוהים במבחן: אכל בשר-חזיר ביום-הכיפורים, לא נענש וחדל להאמין. הוא עזב את בית הוריו, נדד ברחבי גרמניה, התיידד עם פוחחים, נשכר לעבודות מכל הבא ליד, ופרש מהן. ב-1923 התגלגל לארץ-ישראל, ועבד בה כחקלאי, כשליח ודייל בבית-מלון בעיר העתיקה, וכמשרת בבית הקונסול ההולנדי בירושלים. אחרי זמן-מה הפליג לאיטליה, עבד במפעל טקסטיל במילאנו, צבר כסף, נסע למונטה-קרלו והפסיד בהימורים את כל כספו. משם נסע לעיר-מולדתו. עבד בימים בבית-המסחר לתוצרת-עור של אביו, ובלילות, בשותפות עם שומרת של בית-שימוש ציבורי, מכר תיקים ליצאניות. ב-1926 התגייס ללגיון הזרים הצרפתי, שירת בו חמש שנים, השתתף בקרבות במדבר סהרה ובהרי-האטלס, וקיבל דרגת רב-סמל ואת עיטור השירות המצוין. אחרי זאת קיבל משרת סוכן בחברת-הנפט "של" בפאריס, ונשבה בקסמי תרבותה, מטבחיה ויינותיה של עיר-האורות. ב-1934 חזר לארץ-ישראל ועבד כשומר על חתולים וארנבים ששימשו בניסויים במעבדות האוניברסיטה העברית. מצוקת בעלי-החיים נגעה לליבו, הוא שילח אותם לחופשי ופוטר מעבודתו. אחר-כך עבד בבניין ובשמירה בכרמים, והתגייס לארגון ה"הגנה".
מפקדי-ה"הגנה" כיבדו את האיש בעל-התרבות המערבית, ששירת בלגיון הזרים האגדי, ושאלתיאל, שהיה, בעקבות שיטוטיו הרבים, צמא לאוטוריטה, ראה בהם אנשים היודעים את אשר לפניהם. ברל כצנלסון התרשם שיש בשאלתיאל "ניצוץ של תושייה" ושהוא מכיר היטב את אירופה המערבית, והמליץ עליו לפני אליהו גולומב,
משה שרת ושאול אביגור. לשאלתו של שרת, "אתה יודע מה ברצונך לעשות?" ענה שאלתיאל: "להיות נושא-כלים של העם היהודי." סגנון זה הרשים את מנהיגי הישוב ופתח דלתות לפני שאלתיאל.
בשנת 1935 שלחו גולומב ואביגור את שאלתיאל לאירופה לרכוש נשק, תחת הכיסוי של שליח מארץ-ישראל בתנועת "החלוץ" בפאריס. שאלתיאל רכש נשק בבלגיה, ובגרמניה, אף שכבר הייתה תחת שלטון הנאצים. הוא כתב: "רוב הזמן הייתי בפאריס, ובסוף השבוע הייתי נוסע ליום-יומיים לאנטוורפן. היה לנו קשר עם ברונו ספירו, סוחר נשק מהמבורג (ידיד של משפחת שאלתיאל), שהיה בא לבלגיה. קנינו ממנו חמש מאות רובי 'מאוזר', במחיר שלוש לירות שטרלינג הרובה, וכן 'מאוזרים' בעלי מחסניות של עשרים וחמישה כדורים." את כלי-הנשק שרכש אָרָז שאלתיאל בחביות מלט לבן' והביא אותן לנמל אנטוורפן. ישראל גלילי יצא לאנטוורפן, למד לזהות את החביות, ולקח אתו לארץ-ישראל תעודות-משלוח על-שם יוסף קטן (השם נבחר מספר הטלפונים). באוקטובר 1935 הגיע לנמל יפו המשלוח השלישי של חביות-המלט, באונייה הבלגית "לאופולד השני". חמש מאות שלושים ושבע חביות, שעברו בנמל בדיקה שגרתית ונמצאו כשרות. למחרת אירעה תקלה: אחת החביות נשמטה ונפלה במהלך ההעברה. המכסה שלה נפתח והכדורים הדרדרו ממנה על הרציף. כל המטען הוחרם, והשלטונות הבריטיים פתחו בחקירה: מי שלח את המטען מאירופה ומי עמד לקבל אותו בארץ-ישראל.
גלילי נסע לפאריס, טשטש עקבות, חיפש שיטות-משלוח חדשות ונסע עם שאלתיאל להמבורג. שם הראה לו שאלתיאל משלוח של זכוכית לחלונות-ראווה, שבו נטמנו אקדחים רבים. בתוך גרמניה הנאצית לא הראה שאלתיאל סימני פחד, ואף לא סימני-זהירות. גלילי הביא אתו מברלין מזוודה עם מאה אלף מארקים, שנתנו לו השליחים, אנצו סירני ואהרון ציזלינג, ושאלתיאל לקח אותו אל סוחר-הנשק ספירו. אשתו של ספירו, לא-יהודיה, ומאהבה, הפקיד הראשי שלו, הלשינו לשלטונות על עסקי הבעל היהודי. ספירו ושלתיאל נאסרו בידי הגסטפו, הידיעה על מאסרם של שאלתיאל וספירו הגיעה אל גלילי כששהה בפאריס. השניים נחקרו בעינויים קשים, וספירו התאבד במעצר. שאלתיאל נחקר בעינויים חמישה-עשר חודשים ולא נשבר, ואחר-כך נשלח למחנה-הריכוז בדכאו. שמונה חודשים הוא שהה שם והיה למנהיג האסירים. שליחת "הקיבוץ המאוחד" לגרמניה, יוכבד בת-רחל, וסוחר יהודי שהיה קשור למפלגה הרוויזיוניסטית, הצליחו לקבל ממנו ידיעות, ומנהיגי הישוב בארץ-ישראל ביקשו מהשלטונות הבריטיים לסייע לשחרורו. בד-בבד הטילו על פנחס (פינו) גינזבורג, שהיה שליח-עליה בגרמניה, לפעול לשחרור שאלתיאל. גינזבורג קשר קשרים עם אישים נאצים וביקש מהם להשתדל ששאלתיאל ישוחרר עד 31 במארס 1939, בטענה שבתאריך זה יפוג תוקף רישיון-הכניסה שלו לארץ-ישראל. שאלתיאל שוחרר ב-30 במארס, וחזר לארץ-ישראל כחצי שנה לפני שפרצה מלחמת העולם. בארץ-ישראל השתתף בפעולת-גמול ונעצר כחשוד ברצח שלושה ערבים. אשמתו לא הוכחה, והוא שוחרר בתחילת שנת 1940. כשהוקמה "מחלקת הריגול הנגדי" (ר"ן) היה המנהל-בפועל שלה, יחד עם יהודה ארזי; אחר-כך מונה ארזי לאיש-קשר של ה"הגנה" עם הבריטים, ו
זאב שרף הצטרף אל שאלתיאל במקומו. שניהם הקימו את שירות הידיעות של ארגון ה"הגנה".
בשנת 1942 העביר שאלתיאל את הפיקוד על הש"י לישראל עמיר, מונה למפקד מחוז-חיפה, והכין את אזור הכרמל לקראת אפשרות פלישה של צבא גרמני, במסגרת "תוכנית הצפון".
1 בסוף שנת 1943 מסר את הפיקוד על חיפה ליוסף בן-פורת, וב-1944 נשלח לאירופה המשתחררת, כדי לקשור קשרים עם ניצולי השואה. ב-1945 נפגש עם ראשי המחתרת היהודית בצרפת, ושכנע אותם לא לפרק את ארגונם אחרי הניצחון על גרמניה, אלא לסייע לעקורים בני עמם לעלות לארץ-ישראל, לאמן אותם ולרכוש נשק למען ה"הגנה". בימי "תנועת המרי" מונה ל"קצין לתיאום מבצעים נגד הבריטים". ב-1946 סיים ישראל עמיר את תפקידו כראש הש"י (וקיבל את הפיקוד על ירושלים) ושאלתיאל קיבל שוב את הפיקוד על הש"י. בתחילת פברואר 1948 מונה למפקד ירושלים.
בספר שהוקדש לזכרו כתוב (באהדה): "מיום שעמד על דעתו נקרע דוד בין תחושת הכבוד והמסירות למסורת, לאביו ולכל הערכים (ש)אותם ייצג, לבין דחפיו ויצריו הטבעיים שהורוהו למרוד במוסכמות ולחיות לפי צו ליבו וכרצונו."
2 ספק, לכן, אם זה היה האיש המתאים לפקד על ירושלים בשעתה הקשה. אף שהייתה לו הילה של לוחם נועז, והיה לו ניסיון בפיקוד על עיר, אף שלמד, בתפקידו בש"י, פרק במדיניות ובפוליטיקה הפנימית, ואף שבן-גוריון סמך על נאמנותו.