מזרחי גדל בקבוצת הנוער של הפועל ירושלים ובגיל 17 עבר ליריבתה העירונית, בית"ר ירושלים. מזרחי עלה לקבוצת הבוגרים של המועדון בשנת 1974, והחליף את יוסף סורינוב בתפקיד השוער. מזרחי שיחק בקבוצה במשך 14 עונות ברצף, ושיתף פעולה עם שחקנים בולטים בהיסטוריית המועדון כדוגמת אורי מלמיליאן, אלי אוחנה ודני נוימן. מזרחי זכה עם בית"ר ירושלים באליפות המדינה בעונת 1986/1987, וארבע פעמים זכה עמה בגביע המדינה כשוער ראשון. לפני פרישתו ממשחק פעיל שיחק מזרחי עונה אחת בהפועל לוד[1] ושתי עונות נוספות בשמשון תל אביב, עד שתלה את הכפפות ב-1991, כשהוא בגיל 38.
בנוסף את הופעת הבכורה שלו בנבחרת ישראל ערך בשנת 1981 מול נבחרת פורטוגל, ולזכותו של מזרחי ישנן 9 הופעות במדים הלאומיים של ישראל.
לאחר פרישתו ב-1991 החל לאמן לראשונה ביריבה העירונית הפועל ירושלים. ב-1994 החל לאמן בבית"ר ירושלים, תחילה כעוזר המאמן של אמציה לבקוביץ' ומאוחר יותר כמאמן הראשי. לאחר מכן חזר לאמן בהפועל ירושלים והמשיך למכבי פתח תקווה, וחזר ב-2002 לאמן את בית"ר לקדנציה קצרה, וכן שימש כעוזר מאמן נבחרת ישראל, תחת אברהם גרנט. לאחר מכן אימן שנתיים במ.ס. אשדוד.
בעונת 2006/2007 שב מזרחי לבית"ר ירושלים והוביל את הקבוצה לזכייה באליפות. אף על פי כן, בסיום העונה החליטה הנהלת בית"ר בראשות ארקדי גאידמק כי מזרחי לא ימשיך בתפקידו. בעונת 2007/2008 חתם מזרחי במכבי פתח תקווה והחליף בתפקיד את גיא לוזון. לאחר פתיחת עונה טובה, עזב מזרחי את הקבוצה וחתם בקבוצה הקפריסאיתאפולון לימסול. בסיום העונה בקפריסין הצטרף מזרחי למ.ס. אשדוד ועזר לקבוצה להישאר בליגת העל.
במאי 2013 סיים מזרחי את תפקידו כמאמן אשדוד, וחתם בקבוצת מכבי נתניה לאחר שירדה לליגה הלאומית. בעונתו הראשונה בקבוצה הוביל אותה בחזרה לליגת העל, לאחר שסיימה במקום הראשון בליגה הלאומית, וכן העפיל עמה לגמר גביע המדינה, בו הפסידה הקבוצה לעירוני קריית שמונה. ב-14 בינואר2015 התפטר מזרחי מאימון הקבוצה בעקבות מספר כישלונות והמצב הכלכלי הקשה אליו נקלע המועדון.
ב-24 במאי2020 חזר מזרחי לקבוצת נעוריו בית"ר ירושלים בפעם הרביעית, הפעם חתם שם כמאמן קבוצת הנוער של המועדון ואחראי על איתור והשבחת שחקנים צעירים[5]. ב-28 באוגוסט2020 מונה למאמן קבוצת הבוגרים באופן זמני לאחר פיטורי רוני לוי מהמועדון ולאחר מכן חזר לתפקיד מאמן הנוער. ב-27 באוקטובר2020 הודיעה בית"ר על מינויו של מזרחי לתפקיד המנהל המקצועי של מחלקת הנוער במועדון. ב-21 במרץ2021, מונה למאמן בית"ר ירושלים באופן זמני פעם נוספת עד תום העונה, וזאת לאחר התפטרות צמד המאמנים שי ברדה וסלובודאן דראפיץ' עקב כישלון הקבוצה, לאחר מכן חזר לתפקידו המקורי בתור מנהל מחלקת הנוער. לאחר מכן ב-9 בדצמבר 2021 מונה למאמן ביתר ירושלים בקדנציה השישית שלו במועדון, וזאת עד סוף עונת 2021/2022[6] במקומו של המאמן ארווין קומאן שהתפטר מהקבוצה עקב כישלונה בליגה. ב-26 בינואר 2022 סיים את תפקידו הזמני, ושב לתפקידו כמנהל המקצועי של מחלקת הנוער.
ביולי 2023 הצטרף יוסי מזרחי אל קבוצת בית״ר נורדיה ירושלים כמנהלה המקצועי, תפקיד אותו הוא ממלא בשותפות עם שחקן העבר משה בן ארוש.