היעד שבו הוחזקו החטופים העמיד בעיה קשה בפני ממשלת ישראל, הן בגלל המרחק הרב שלו מגבולות ישראל, והן בגלל, שהחוטפים נהנו משיתוף פעולה מלא של שליט אוגנדה, אידי אמין. לכן נטו בתחילה ראש הממשלה דאז, יצחק רבין ז"ל, וקברניטי מערכת הבטחון, שלא לאשר פעולה צבאית לשחרור החטופים.
"כשהמטוס נחת באנטבה הבנתי לראשונה שזו תהיה בעיה שלנו, בעיה שמדינת ישראל תצטרך לפתור בעצמה", סיפר (לבטאון חיל-האוויר) שיקי שני, מפקד טייסת 131 בזמן החטיפה ומוביל המטוסים, שהנחיתו את כוח צה,ל באנטבה. "המחשבה הראשונה שעברה לי בראש היתה 'מה לנו ולזה'. המטוס הוא צרפתי, שממשלת צרפת תתמודד עם הבעיה. אבל מאה ישראלים באנטבה, זו כבר בעיה שלנו".
בישיבת צוות השרים ב-29 ביוני, יומיים לאחר החטיפה, העלה לראשונה ראש הממשלה את אפשרות קיום המבצע הצבאי לשחרור החטופים.
הוחלט, כי מדינת ישראל תתחיל לנהל משא ומתן עם החוטפים, ובמקביל יתחיל צה"ל לתכנן מבצע צבאי לשיחרורם, שיהווה אופצייה משנית. ב-1 ביולי הודיעו החוטפים, כי הם מאריכים את האולטימטום שלהם ב-4 ימים נוספים, פרק זמן, שאיפשר שהות נוספת לתכנון האופציה הצבאית.
"כבר ביום ראשון בערב, יום החטיפה, התחלנו לחרוש מזימות", סיפר שיקי שני. "מהרגע הראשון היה ברור לנו כי היכולת היחידה להגיע לאנטבה היא במטוסי הרקולס. נכנסנו להילוך גבוה של תכנון מבצעי, וביום רביעי כבר היינו עם תוכנית מפורטת". התוכנית, שכונתה בשם הקוד 'כדור הרעם', כללה נחיתה של ארבעה מטוסי הרקולס, ועליהם כוח סיירת מטכ"ל וכוחות נוספים בנמל התעופה של אנטבה, השתלטות עליו ועל בניין הטרמינל הישן שבו, ושחרור החטופים.