פאולו סוזה מונה למאמן מכבי תל אביב לקראת עונת 13/14. את קריירת האימון שלו החל סוזה תחת ההתאחדות הפורטוגלית כשהתמנה בקיץ 2008 כעוזרו של מאמן הנבחרת הבוגרת לואיס פיליפה סקולארי ובמקביל אימן בנבחרות הצעירות של פורטוגל. בנובמבר 2008 מונה סוזה כמאמן קווינס פארק ריינג'רס ולאחר שייצב את הקבוצה, סיים את תפקידו באפריל 2009 ומונה בקיץ כמאמנה של סוונסי סיטי מווילס. סוזה, הצעיד את 'הברבורים' למיקום הגבוה ביותר שלהם ב-27 שנה כשסיים במקום השביעי בליגת המשנה האנגלית. ארבעה ימים אחרי שנפרד מסוונסי, הוחתם סוזה כמאמנה של לסטר סיטי.
לאחר שלוש שנים באי הבריטי, מונה סוזה במאי 2011 כמאמנה של אלופת הונגריה וידיאוטון איתה זכה בסופרקאפ, בגביע הליגה ההונגרי וסיים את הליגה במקום השני בטבלה תוך שהוא קובע באותה עונה שיא צבירת נקודות למועדון. בעונתו השנייה בוידיאוטון, זכה שוב בסופרקאפ ההונגרי והצעיד את המועדון להישגו הגדול ביותר ב-25 השנים האחרונות: שלב הבתים של האירופה ליג, כשבדרך הוא מדיח את סלובן בראטיסלאבה, גנט הבלגית וטראבזונספור הטורקית. ניצחונות על ספורטינג ליסבון ובאזל העניקו לוידיאוטון את המקום השלישי בבית G כשבחודש ינואר באותה שנה נפרד סוזה מהקבוצה ההונגרית.
במכבי רשם סוזה הצלחות בזירה המקומית והבינלאומית. בליגה הצעיד המאמן הפורטוגלי את הצהובים לאליפות שנייה ברציפות שנלקחה בצורה מרשימה עם פער של 16 מהמקום השני. בנוסף מכבי נהנתה עם סוזה מעונה אירופית מצוינת כאשר המאמן הוביל אותה להצלחה בשלב הבתים של האירופה ליג והגעה לשלב 32 האחרונות שם הודחו הצהובים ע"י באזל. אלופת שוויץ הייתה גם התחנה הבאה של סוזה שלאחר עונה אחת בקרית שלום החליף את מוראט יאקים כמאמן באזל.
