ביום 12.7.1931, כשבועיים לאחר שיוחנן וסליה יצאו לטיול נדפסה ב
עיתון "דבר" ידיעה בדבר היעלמם של השניים, ואז החלו החיפושים. המשטרה הבריטית שלחה שוטרים אנגלים, יהודים וערבים, לחפש אחר הנעדרים. ואף מטוס של הצבא הבריטי הועלה לאוויר לסרוק את החוף עד חדרה. בחיפושים נטלו חלק גם אחיה של סליה צבי זוהר, וגיסה של סליה משה זלצר, אשר יחד עם חבריהם סרקו את השטחים שבין הירקון להרצליה. אולם כל החיפושים לא העלו דבר.
משלא העלו החיפושים אחר השניים דבר, הכריזו הבריטים על מתן פרס של 20 לא"י למי שימסור אינפורמציה שתביא לפתרון התעלומה. בהודעה רשמית מטעם שלטונות המנדט מתאריך 1 באוגוסט 1931 שפורסמה בעיתונות בארץ בשלוש שפות, אנגלית, עברית וערבית, נאמר בזו הלשון: "פרס של עשרים 20) פונטים פלשתינים (א"י) ישולם לאיש אשר יהיה הראשון שימסור ידיעות שיובילו למציאתם של: סליה זהר ויוחנן שטאל, שעזבו את תל אביב ב־28 ביוני 1931 לטיול קצר ולא שבו. במודעה מובא תיאורם של שני הנעלמים וכן תמונותיהם. להלן תיאורה של סליה זוהר כפי שמופיע במודעה : גבהה 168 ס"מ רזה, מראה חום, שער שחור, עיניים חומות, בפעם האחרונה שראוה הייתה לבושה בשמלה קצרה עד הברכיים, וסנדלים בלי גרבים, ונשאה נרתיק־ יד, מדברת פולנית, גרמנית ועברית.
תיאור יוחנן שטאל: בן 23 גבהו 163 ס"מ מבנה גוף בינוני, שיער בהיר, עיניים כחולות, בפעם האחרונה שראוהו היה לבוש בכתונת "חאקי" עם צווארון פתוח, מכנסים קצרים, של " חאקי" סנדלים בלי גרבים ונשא שק (רוקזאק) ירוק על גבו. מדבר גרמנית ועברית. חתום על המודעה ר. ג . ב . ספייסר מפקד המשטרה.
מפקד המשטרה הבריטית בא"י המפקח ספייסר אמר למנהל סט"א (סוכנות טלגרפית ארצי-שראלית) מר שוארץ: " מתקבל על דעתי ששטאל וזוהר עזבו את הארץ ואולי תקבלו בעוד זמן מה מכתבים מהם" .
בעיתונות היהודית האשימו את המשטרה הבריטית שאינה מתאמצת במיוחד לפתרון התעלומה. ולברר מה עלה בגורלם של שני היהודים שנעלמו. העיתונות היהודית גם מתחה ביקורת על הסכום הנמוך- 20 לא"י שהציעה המשטרה הבריטית למוסרי מידע שיביא למציאת יוחנן וסליה. וכך נכתב למשל בטור מערכת של העיתון "דבר" מיום 16 ביולי 1931: "שני אנשים סליה ויוחנן יצאו לפני 17 יום לטיול בן יומיים שלושה ומאז לא נתקבלה מהם כל ידיעה. כל ההשערות שהיו עלולות להשקיט את הדאגה לגורלם, אינן מתקבלות על דעת קרוביהם וחבריהם של הנעלמים. אין כל יסוד לחשוב על בריחה, נסיעת פתאום לחו"ל או התחבאות. כל התנאים והמסיבות מכריחים להניח, כי קרה אסון והחרדה רבה. כל מי שנזדמן לו להיפגש את השניים האלה או לשמוע משהו עליהם ועל עקבותיהם, אל יחמיץ ויבוא מיד לעזרת המחפשים.... אולם בראש ובראשונה מוטלת חובת החיפוש על ממשלת הארץ... לאן נעלמו האנשים ? המשטרה נדרשת להעמיד את כל כוחותיה, את כל כשרונה לשירות החיפוש. אל ילך לאיבוד אף יום אחד, אל תידחה חקירה נמרצת אף לשעה אחת. לא רק גורל שני האנשים שנעלמו מחייב זאת, עצם ביטחון החיים בארץ דורש זאת!".
גם מוסדות הסתדרות העובדים, הוועד הלאומי ומחלקת הביטחון של הסוכנות היהודית הצטרפו לחיפושים. ארגון ה"הגנה" פנה לאנשיו לחקור היכן נטמנו הגוויות; היה ברור לארגון זה שהנעלמים כבר אינם עוד בין החיים. מפקד ההגנה, אליהו גולומב, כינס בביתו בתל אביב שורה של בכירי "ההגנה" ובהם דוד זסלבסקי, מראשוני גבעת-ברנר, מאיר ספקטור, מוותיקי "השומר" יהושע אייזיק (לימים אשל) איש "גדוד העבודה" והורה לארגן חיפושים למציאת הנעלמים " - עלינו להגיע לפתרון התעלומה ויהי מה" אמר גולומב.
פעילי "ההגנה" ובהם שאול מאירוב (לימים אביגור) מקבוצת כינרת, צבי ניסנוב מטבריה, צבי וולף מבית-אלפא, חיים שטורמן מעין-חרוד, הלל לנדסמן מאילת-השחר, נחום הורביץ מכפר-גלעדי ואחרים. פעלו והפעילו חברי "ההגנה" וכן סוכנים ומודיעים של "ההגנה" כדי לנסות ולברר מה עלה בגורלם של שטאל וסליה. הם ערכו חקירות וחיפושים ביישובים ובכפרים ערביים, ובין שבטי הבדווים, אולם כל המאמצים לגלות את עקבות הנעלמים עלו בתוהו.
המשורר הצעיר יונתן רטוש (אוריאל היילפרין), שעבד באותה עת כמורה במושבה הרצליה, פרסם ב-7 באוגוסט 1931 (כחודש וחצי לאחר היעלמותם של יוחנן וסליה) בעיתון הרביזיוניסטי "העם" את שירו "כי ישאלך". בשיר זה תוקף המשורר את מורך הלב של הנהגת היישוב מתנועת העבודה שבניגוד לחוגים הלאומיים, ביקשו להמתין לתוצאות החקירה ולא להאשים ברצח את כפריי הסביבה הערבים.