במלחמת העצמאות, הצליח למרות עברו, להצטרף לחטיבת הראל בתפקיד קצין מנהלה בדרגת סגן. הוא נתפס כשעסק במכירת מזון ודלק ממחסני החטיבה בשוק השחור בירושלים ובהברחת אזרחים מהעיר הנצורה בכלי רכב צבאיים. בעקבות זאת הודח מן החטיבה, ושוב הצליח להסתנן ליחידת עילית, הפעם ליחידת הצנחנים, שהוחלט על הקמתה בשלהי מלחמת העצמאות. בסוף שנת 1948 שימש כמפקד פלוגה בבית הספר לצניחה בחיפה. הוא הודח מן היחידה כשנמצא שהוא עוסק בהדרכת צניחה מבלי שצנח מעולם בעצמו.
בשנותיו הראשונות של צה"ל, כשטרם התגבשו הליכי מיון כוח אדם והליכי סיווג ביטחוני מסודרים, הצליח אלעד להתקבל לקורס מפקדי גדודים בצריפין. בסיום הקורס התמנה לסגן מפקד גדוד שהורכב ברובו מאסירים ששוחררו בחנינה הכללית שהוכרזה לקראת תום מלחמת העצמאות. בשנת 1951 גנב מיחידתו מקרר חשמלי גדול והעבירו לביתו. הדבר התגלה ואלעד נידון להורדה לדרגת טוראי ולסילוק מן הצבא.
שובו לצה"ל.
בראשית שנות החמישים, בתקופת התגבשותה והתארגנותה של קהילת המודיעין, דגלו ראשי מחלקת המודיעין הצבאי - אג"ם ממ"ן ולאחריה (החל מ-28 בדצמבר 1953) אגף המודיעין במטכ"ל, בגישה שלפיה ניתן לנצל את שאיפתם של בעלי עבר פלילי לטהר את שמם, לשם גיוסם למשימות קשות ומסוכנות. הסברה הייתה כי ככל שהעבריין קשוח יותר, הוא יהיה כשיר לביצוע פעולות נועזות יותר. בשני מקרים ידועים נהגו כך, והדבר הביא לכישלונות ביטחוניים ומוסריים. המקרה אחד היה פרשת מרדכי קידר ("האסיר X") שהורשע בשוד ורצח של סייען יהודי מקומי בארץ היעד. המקרה השני, שהביא לאסון של ממש ברמה הלאומית היה פרשת האדם השלישי, היא פרשתו של אברי אלעד.
לאחר סילוקו מן הצבא, עבד אלעד במפעל קייזר-אילין תעשיות להרכבת רכב. אברהם דר מפקד יחידה 131 של חיל המודיעין (היחידה החשאית לפעולות מיוחדות בארצות האויב) שהכיר את אלעד, סבר שהוא מתאים, לפי הקונספציה האמורה, למילוי משימה של מרגל במדינת אויב. אחרי התייעצות עם ראשי המודיעין הצבאי, הוחלט שאלעד יוכל להשיג רהביליטציה, ולהחזיר לעצמו את כבודו ודרגתו באמצעות משימה בארץ אויב. אלעד עבר אבחון אצל הפסיכולוג של המודיעין הצבאי, ד"ר דוד רודי, שמצא אותו מתאים למשימה.
ב-1 בספטמבר 1952 התקבל אלעד לניסיון ליחידה 131. ראש מינהל הסגל, יוסף גבע, התנגד לגיוסו בהכירו את האיש ומעלליו, אך ב-23 במרץ 1953, כשהיה ראש מנהל הסגל בחופשה, הוחתם אלעד על חוזה שירות והוחזרה לו דרגת הקצונה. זמן קצר לאחר מכן, יצא לשווייץ ומשם לגרמניה לשם בניית זהות כיסוי של גרמני נוצרי בשם פאול פרנק, לשעבר קצין בוורמאכט, הפועל במצרים כנציג חברה מסחרית גרמנית.
בתקופת שהותו בגרמניה, ובעודו ממלא תפקיד ביטחוני רגיש, חזר אלעד לסורו, נהג בהוללות ובפזרנות, רכש מכונית אמריקאית מפוארת והתפאר ברבים כי הוא איש מודיעין ישראלי.
הידיעות על התנהגותו של אלעד הגיעו לידיעת אמ"ן. נציג אמ"ן יצא לפגוש את אלעד בפריז לשם מתן הערכה על כשירותו לתפקיד. הקצין נזף באלעד, אך המשיך לדבוק בקונספציה, והחליט כי האיש כשיר לשליחותו.
אברי אלעד במצרים - "העסק הביש".
ב-23 בדצמבר 1953 הגיע אלעד לראשונה למצרים. הוא ניהל במצרים אורח חיים ראוותני, נהג במכוניתו האמריקאית, והציג עצמו (בסטייה מן הכיסוי שנתפר לו) כמהנדס מכונות, איש קהילת הטמפלרים מארץ ישראל שהיה אחד מן הצנחנים הגרמניים שצנחו בבקעת הירדן במבצע אטלס בשנת 1944. לאחר שהות של מספר חודשים, במאי 1954, נקרא אלעד לפריז לפגישה עם מרדכי בנצור, שהחליף את אברהם דר כמפקד יחידה 131. בפגישה זו הוטלה עליו הפעלת רשת שליחי היחידה במצרים שהורכבה מיהודים מקומיים (שנודעו לאחר מכן כ"נידוני קהיר").
בקיץ 1954, הגיעה ההוראה להפעיל את הרשת. המטרה הייתה לבצע פיגועים באתרים בריטיים ואמריקנים בקהיר ובאלכסנדריה. הפיגועים נועדו לעורר את הרושם כי הם מעשי ידיהם של לאומנים מצריים, ועל ידי כך להביא לערעור היחסים בין מצרים לבין מעצמות המערב, ובזאת למנוע את פינוי הצבא הבריטי מאזור תעלת סואץ.
התוכנית נכשלה, מעשי החבלה היו חובבניים ו-13 חברי הרשת (שפעלה באופן חשאי עוד משנת 1951 מבלי שנחשפה) נתפסו ביולי 1954 והועמדו לדין. שניים מהם - משה מרזוק ושמואל עזר - נידונו למוות והוצאו להורג, והאחרים נידונו לתקופות מאסר שבין שבע שנים למאסר עולם. שניים מהנשפטים זוכו. כן נחשף, בעקבות נפילת הרשת, סוכן מודיעין ישראלי שפעל במצרים, בנפרד מן הרשת, רב-סרן מאיר בינט, שנעצר ושם קץ לחייו בכלא המצרי. אלה מהנידונים שעדיין נותרו במאסר בשנת 1968, שוחררו בשנה זו, במסגרת חילופי השבויים עם מצרים שלאחר מלחמת ששת הימים. נידוני קהיר לא שוחררו במסגרת חילופי השבויים שלאחר מבצע קדש משנת 1956, על אף שבידי ישראל היו כ-5,500 שבויים מצריים ובהם הגנרל דיגאווי, מושל רצועת עזה, שהיה אב בית הדין שדן את נידוני קהיר.
יש הסוברים כי אחד מיסודות הכישלון של העסק הביש הייתה העמדתו של איש פלילים הרפתקן בראש הפעולה. עם כישלון הפעולה נטש אלעד את אנשיו ועזב את מצרים, אך לא מיד, אלא ימים לאחר שחברי הרשת נעצרו. הוא עשה זאת בניחותא, כשהוא מוכר את מכוניתו ומפליג ממצרים בספינה לאירופה.
בישראל התחוללה סערה מדינית ופוליטית שנודעה בשם פרשת לבון, כשעיקר המחלוקת בשאלה "מי נתן את ההוראה" - האם היה זה שר הביטחון, פנחס לבון, או ראש אמ"ן, אל"ם בנימין גיבלי.
תוך כדי מאבק אישי וציבורי זה, נוצר מצב שבו אלעד נהנה מחסינות, למרות האופן החשוד שבו דווקא הוא, מפעיל הרשת, לא נעצר, ואף הצליח לצאת ממצרים בשלווה ובביטחון. אלעד הורחק לאירופה קרוב לוודאי כדי לשמור על שתיקתו. באירופה המשיך בשליחותו בשירות אמ"ן תחת שם הכיסוי פאול פרנק, למרות הסיכוי שיהיה מבוקש על ידי המצרים בשם זה.
בשלהי שנת 1954, הקים ראש הממשלה דאז, משה שרת, ועדת חקירה בת שני חברים, נשיא בית המשפט העליון, השופט יצחק אולשן, והרמטכ"ל הראשון של צה"ל, רב-אלוף יעקב דורי. תפקיד הוועדה היה לקבוע מי נתן את ההוראה. הכינוי שניתן לוועדה היה ועדת אולשן-דורי.
אלעד הובא לישראל להעיד בפני הוועדה. בעדותו, תמך בגרסתו של בנימין גיבלי כי את ההוראה נתן פנחס לבון. שני חברי הוועדה לא הצליחו להגיע לידי מסקנה בדבר האחראי למתן ההוראה, ושר הביטחון, לבון, שלא נוקה על ידי הוועדה, התפטר מתפקידו ב-2 בפברואר 1955.
חשיפת בגידתו של אלעד.
בשנת 1957 הגיע לאמ"ן, שגיבלי כבר לא עמד בראשו, מידע, שלפיו מקיים אלעד קשרים עם המודיעין המצרי, באמצעות איש הנספחות הצבאית המצרית בגרמניה. נספח צבאי זה היה אחד מהחוקרים שחקרו את חברי הרשת בשנת 1954.
אלעד הובא לישראל, ונעצר בידי הש"ב. הוא נחקר על מגעיו עם המצרים, ולראשונה הועלתה בחקירתו הטענה כי הוא זה שהסגיר את הרשת למצרים. הוא נעצר תוך כדי חקירתו, לאחר שהשיב תשובה מהוססת לשאלה אם בגד במדינת ישראל. חוקר הש"ב צבי אהרוני, שעצר אותו, סיפר לימים שהחליט על מעצר מיידי לשמע תשובתו של אלעד, "כיוון שמי שלא בגד מימיו במדינת ישראל לא צריך לחשוב אפילו רגע. הוא יאמר מיד: לא".
צה"ל והמוסד הקימו ועדת חקירה לבירור החשדות שהתעוררו בחקירתו של אלעד. בראש הוועדה עמד אל"ם אריאל עמיעד, והכינוי שניתן לוועדה היה ועדת עמיעד. הוועדה התמקדה בחשד כי אלעד הוא שהסגיר את הרשת למצרים. היא נתבקשה לחקור אם יש די ראיות להעמדתו של אלעד לדין על הסגרת הרשת. לפי מסקנות הוועדה, הוחלט להעמיד את אלעד לדין על אישומים פחותים, שלגביהם היו ראיות מוצקות: החזקת מסמכים סודיים וקיום מגע עם האויב.
במשפטו, שנערך בדלתיים סגורות, טען אלעד להגנתו כי הפעיל את הרשת, לפי הוראת ראש אמ"ן, בנימין גיבלי, וכי הודח על ידי אנשי אמ"ן למתן עדות שקר נגד שר הביטחון, פנחס לבון, בפני ועדת אולשן-דורי ב-1955. לדבריו, נשלח אליו שליח מטעם אמ"ן, לפני ששב לישראל למתן העדות בפני הוועדה, שהורה לו להטיל את האשמה על שר הביטחון, כדי לטהר את ראש אמ"ן. עוד טען אלעד במשפטו כי לאחר נפילת הרשת זויפו מסמכים הנוגעים למתן ההוראה. טענות אלה אוששו, בין היתר, על ידי דליה כרמל, מזכירתו של גיבלי, ויוסי הראל שהתמנה למפקד יחידה 131.
עדותו של אלעד במשפטו, שדלפה לעיתונות, עוררה מחדש את פרשת לבון בדעת הקהל בסוף שנת 1960. התעוררה סערה ציבורית שטלטלה את המדינה במשך שנים רבות, גרמה לפיטורי לבון ב-1961 מתפקידו כיושב ראש ההסתדרות הכללית, ולהתפטרותו של דוד בן-גוריון בשנת 1963 מתפקיד ראש הממשלה ושר הביטחון, לפילוג מפא"י, ולהקמת מפלגת רפ"י בשנת 1965. הסערה נרגעה רק בעקבות מלחמת ששת הימים, שדחקה את הפרשה לצל.
אלעד נידון ב-20 בנובמבר 1960 ל-12 שנות מאסר. ב-2 בינואר 1962 דחה בית המשפט העליון ערעור שהגיש אלעד, אך הפחית את עונשו ל-10 שנות מאסר. בחודש אוגוסט 1964 פתח אלעד בשביתת רעב כדי לקדם את שחרורו בניכוי שליש ממאסרו. בחודש ינואר 1966 פתח בשביתת רעב נוספת לאחר שחלפו למעלה מ-8 שנים מעת שנכלא, וועדת השחרורים הודיעה לו כי אינו זכאי לניכוי שליש מתקופת מאסרו.
עזיבתו את ישראל.
לאחר שריצה את תקופת מאסרו בכלא רמלה, בתנאי בידוד, עזב אלעד לקליפורניה. בשנת 1976 פרסם בארצות הברית את גרסתו בספר בשם "Decline of Honor", שיצא בתרגום עברי בשם "האדם השלישי", ואף פורסם בהמשכים בעיתון "הארץ" (הכינוי "האדם השלישי" נוצר בשנות השישים, כאשר בגין אילוצי הצנזורה הצבאית כונו גיבורי הפרשה בעיתונות בשמות קוד: "הקצין הבכיר", "קצין המילואים", "הגבר", ולאלעד הוענק הכינוי "האדם השלישי", כשם סרט הקולנוע הידוע בהשתתפותו של אורסון ולס).