בשנת 2005 חתם טיוטה על חוזה לשלוש שנים באנדרלכט מליגת העל הבלגית. לאחר מספר חודשים בקבוצת המילואים של המועדון, ערף טיוטה את הופעת הבכורה שלו בקבוצה הראשונה של המועדון במשחק במסגרת הגביע הבלגי בו הפסידה אנדרלכט לוורברודרינג ז'ל לאחר שטיוטה החמיץ פנדל. חודש לאחר מכן ערך טיוטה את הופעת הבכורה שלו בליגת האלופות, בהפסד 1-0 לריאל בטיס במסגרת המחזור השישי בשלב הבתים לעונת 2005/2006. טיוטה ערך את הופעת הבכורה שלו בליגת העל הבלגית רק ב-18 במרץ 2006, כשנכנס כמחליף לקראת סיום המשחק בהפסד 4-0 לבוורן. בהמשך העונה ערך טיוטה הופעת ליגה נוספות, שסיכמה ארבע הופעות שלו בכל המסגרות בעונת . בעונה הבאה ערך טיוטה שלוש הופעות בכל המסגרות, מכיוון שבילה את רוב העונה כשהוא מושבת בשל פציעות.
ההשאלה לרודה.
במשך עונת הושאל טיוטה לרודה מליגת העל ההולנדית, בה שיחק לצד בן ארצו סקו סיסה. ב-2 בספטמבר 2007 ערך טיוטה את הופעת הבכורה שלו במועדון, בניצחון 5-3 על פנלו, ולאחר מכן הבקיע את שער הבכורה שלו במועדון בהפסד 3-1 לפיינורד. לאחר שהרשים ברודה, הפך טיוטה לחביב האוהדים במועדון. ב-27 בדצמבר הבקיע טיוטה את שערו השני בקבוצה, בניצחון 1-0 הירנפיין. ב-4 באפריל 2008, בהופעתו האחרונה במועדון, הורחק טיוטה בדקה ה-33 בהפסד 2-0 לניימכן. טיוטה ריצה עונש השעיה של שני משחקים, ובסך הכל ערך שלושים הופעות ליגה והבקיע שני שערים בכל המסגרות בתקופת השאלתו לרודה.
טוונטה.
בתום העונה הביעה רודה את רצונה להחתים את טיוטה, וכך גם סרקל ברוז'. בסופו של דבר, ב-12 ביוני 2008, חתם טיוטה בטוונטה מליגת העל ההולנדית, ששילמה עבורו כ-750 אלף אירו, על חוזה לארבע עונות ואופציה לעונה נוספת. עם הצטרפותו למועדון הצהיר טיוטה כי הטיל ספק בכך שיזכה לדקות משחק באופן קבוע באנדרלכט אם ישאר בה.
ב-13 באוגוסט 2008 ערך טיוטה את הופעת הבכורה שלו במועדון, בהפסד 2-0 במסגרת פלייאוף ההעפלה לליגת האלופות. ב-30 באוגוסט ערך טיוטה את הופעת הבכורה שלו בליגת העל ההולנדית במדי המועדון, כשפתח בהרכב בתיקו 1-1 נגד רודה במחזור הפתיחה של העונה. ב-18 באפריל 2009, במשחק נגד פיינורד בו הפסידה טוונטה בתוצאה 1-0, הורחק טיוטה לאחר שספג כרטיס צהוב שני. ב-17 במאי שיחק טיוטה בגמר הגביע ההולנדי נגד הירנפיין, בו הפסידה טוונטה בדו-קרב בעיטות עונשין לאחר תיקו 2-2 בתום 120 דקות. בעונתו הראשונה במועדון ביסס עצמו טיוטה כשחקן הרכב קבוע, וערך 41 הופעות בכל המסגרות.
לקראת עונתו השנייה במועדון, קושר שמו של טיוטה עם עזיבת טוונטה, כשקבוצות צרפתיות הביעו עניין בהחתמתו. בסופו של דבר נשאר טיוטה בטוונטה והמשיך להיות שחקן הרכב קבוע. ב-20 בספטמבר 2009 הורחק טיוטה לאחר שספג כרטיס צהוב שני בניצחון 3-2 על אוטרכט. ב-10 באפריל 2010 הבקיע טיוטה את שערו הראשון במועדון, בניצחון 2-0 על הירנפיין. ב-13 באפריל, בהפסד 1-0 לא.ז. אלקמאר, ספג טיוטה כרטיס צהוב שבעקבותיו הושעה ממשחק ליגה אחד. טיוטה חזר מההרחקה במחזור הליגה האחרון, בניצחון 2-0 על נאק ברדה שהבטיח לטוונטה את אליפות הולנד. בסך הכל ערך טיוטה 42 הופעות והבקיע שער אחד בכל המסגרות בעונת .
במהלך השנתיים בהן שיחק בטוונטה, זכה טיוטה למוניטין כקשר נחוש וגמיש עם עין חדה למסירה, כשהוא עורך 58 הופעות ליגה, מבקיע שער אחד ומבשל 14. בעקבות ביצועיו במונדיאל 2010, זכה טיוטה לעניין מצד מספר מועדונים, ביניהם ברמינגהאם סיטי, אך המאמן החדש מישל פרודום התעקש שטיוטה ישאר בטוונטה. טיוטה ערך שתי הופעות ליגה בעונת , לפני שחתם בניוקאסל יונייטד.
ניוקאסל יונייטד.
ב-26 באוגוסט 2010 הצטרף טיוטה לניוקאסל יונייטד מהפרמייר ליג תמורת 3.5 מיליון ליש"ט, לאחר שקיבל אישור עבודה. עם הצטרפותו למועדון, התראיין טיוטה בנוגע למעברו לעיתון המקומי Evening Chronicle, ואמר: "זה כבוד רב עבורי להצטרף למועדון כה מפורסם כמו ניוקאסל יונייטד". הוא קיבל את חולצה מספר 24.
ב-18 בספטמבר ערך טיוטה את הופעת הבכורה שלו במועדון במשחק נגד אברטון בגודיסון פארק. הוא השלים את כל 64 המסירות שלו, ביצע שתי חטיפות, השלים את כל חמשת ניסיונות התיקול שלו והבעיטה היחידה שלו הייתה למסגרת. במהרה הפך טיוטה לשחקן אהוב בקרב אוהדי הקבוצה. ב-8 בינואר 2011 הורחק טיוטה במהלך משחק נגד סטיבנייג' במסגרת הסיבוב השלישי של גביע ה-FA. בעוד שטיוטה הצליח להגיע לכדור לפני ג'ון אשטון, הדרך יוצאת הדופן שלו לעשות זאת גרמה לאשטון להתנגש בו, ולשופט אנדרה מרינר לא הייתה כל ברירה אלא להרחיק את טיוטה. טיוטה ניסה לערער על ההחלטה, אך התאחדות הכדורגל האנגלית בחרה להשאיר את ההחלטה על כנה, וטיוטה הושעה לשלושה משחקים. ב-5 בפברואר הבקיע טויטה את שערו היחיד במועדון, שער שוויון מאוחר בבעיטה מהאוויר מ-25 מטרים בתיקו 4-4 נגד ארסנל, לאחר שניוקאסל יונייטד הייתה בפיגור 4-0 במחצית. ב-25 בפברואר הודיעה ניוקאסל יונייטד שטיוטה חתם על חוזה חדש לשש שנים וחצי במועדון על-מנת להראות את המחויבות שלו לקבוצה. עם החתימה על החוזה החדש, אמר טיוטה: "חוויית המשחק בפרמייר ליג טובה יותר משאי פעם ציפיתי שתהיה. זה מועדון מעולה והאוהדים מבריקים - מעולם לא חוויתי אהדה כזו". בעונתו הראשונה במועדון ערך טיוטה 28 הופעות בכל המסגרות.
את עונת החל טיוטה בצורה מעולה עבור המועדון, ובישל שני שערים בשני משחקים, ב-17 בספטמבר וב-24 בספטמבר 2011, נגד אסטון וילה ונגד בלקברן רוברס, שהובילו לתיקו ולניצחון בהתאמה. עם זאת, ב-22 באוקטובר, במהלך ניצחון 1-0 על ויגאן את'לטיק, הוא סבל משבר באפו ופציעה בברכו, שהשביתו אותו לחודשיים. ב-17 בדצמבר חזר טיוטה למגרשים, כששיחק 82 דקות והוחלף בתיקו 0-0 נגד סוונסי סיטי. לאחר סיום גביע אפריקה לאומות 2012 חזר טיוטה להרכב הראשון של הקבוצה, וב-25 בפברואר 2012 בישל את אחד משני השערים בתיקו 2-2 נגד וולברהמפטון וונדררס. טיוטה ערך 24 הופעות בכל המסגרות בעונת 2011/2012.
בשתי העונות הראשונות שלו בניוקאסל יונייטד, ספג טיוטה 25 כרטיסים צהובים ב-50 משחקי ליגה, ממוצע של כרטיס צהוב אחד בשני משחקים, אך הורחק פעם אחת בלבד, מול היריבה העירונית סנדרלנד בתיקו 1-1 באצטדיון האור ב-21 באוקטובר 2012, בשל תיקול מאוחר בסטיבן פלטשר. ב-22 בדצמבר, בניצחון 1-0 נגד קווינס פארק ריינג'רס, ספג טיוטה את כרטיס צהוב שהיה הכרטיס הצהוב החמישי שלו בעונת עונת 2012/2013, והושעה ממשחק אחד. בסך הכל טיוטה ערך 31 הופעות בכל המסגרות בעונת .
בעונת 2013/2014 שימש טיוטה כקפטן ניוקאסל יונייטד בפעם הראשונה, כשהחליף את פבריסיו קולוצ'יני ואת יוהאן קבאי, שהיו שניהם פצועים, ושיחק היטב בתיקו 2-2 נגד ליברפול ב-19 באוקטובר 2013. לאחר המשחק, טיוטה קיבל שבחים עבור תפקודו כקפטן על ידי המאמן אלאן פארדיו, שרצה שטיוטה ישמש כקפטן במשחק נוסף. ב-12 בינואר 2014, בהפסד 2-0 למנצ'סטר סיטי, שער של טיוטה נפסל באופן מעורר מחלוקת. בדומה לשער השוויון נגד ארסנל שנתיים לפני כן, טיוטה בעט כדור מהאוויר מחוץ לרחבה, שעבר את ג'ו הארט, שוערה של מנצ'סטר סיטי. השופט מייק ג'ונס חשב שיואן גופראן, אשר היה בעמדת נבדל, חסם את שדה הראייה של הארט, על-אף ששידורים חוזרים העידו כי לא כך היה המקרה. כמו במשחק נגד ארסנל, טיוטה חגג בריצה לעבר ספסל קבוצתו. בו זמנית, הארט עם כמה מחברי קבוצתו, מחו על ההחלטה באוזני הקוון, ובעוד רוב שחקני ניוקאסל יונייטד רחוקים מהמגרש (רק קבאי היה בקרבת הקוון), השער נפסל. אנשי כדורגל גינו את ההחלטה לפסול את שערו של טיוטה. מאוחר יותר באותו החודש, קבאי עזב את הקבוצה על-מנת להצטרף לפריז סן-ז'רמן ופרק את השותפות המצוינת בינו לבין טיוטה. כתוצאה מכך, טיוטה סבל מירידה ברמה, שכן דן גוסלינג, מחליפו של קבאי, לא הגיע לרמה הנדרשת. עם זאת, טיוטה קיבל את סרט הקפטן בהיעדרותו של קולוצ'יני, שסבל מפציעה בברכו במשחק נגד וסט ברומיץ' אלביון. טיוטה ערך 36 הופעות בכל המסגרות בעונת .
טיוטה החל את עונת באיחור בשל פציעה בירך, והוא ערך את הופעתו הראשונה בהרכב הפותח בעונה זו ב-20 בספטמבר 2014, בתיקו 2-2 נגד האל סיטי, בו בישל את אחד מצמד השערים של פאפיס סיסה. טיוטה ערך עשר הופעות נוספות בליגה, לפני שנעדר מקבוצתו בשל השתתפותו בגביע אפריקה לאומות 2015 עם נבחרת חוף השנהב. בטורניר הוא סבל מפציעה בברכו, והיה צריך לעבור ניתוח שהשבית אותו לשאר העונה. הפציעה פגעה ברוחו של השחקן, והוא הצהיר בפני התקשורת בחוף השנהב שהוא רוצה לעזוב את ניוקאסל יונייטד. לפני כן שמו קושר עם מעבר אפשרי לארסנל או למנצ'סטר יונייטד, והוא הודה שהיו מגעים עמו מכיוון ארסנל וקבוצה רוסית.
בעונת 2015/2016 ערך טיוטה 20 הופעות ליגה עבור קבוצתו, תחילה תחת המאמן סטיב מקלארן ולאחר מכן תחת המאמן רפאל בניטס. אף על פי כן, לא היה ביכולתו לפרק את הצימוד בין מוסא סיסוקו וג'ורג'יניו ויינאלדם בקישור, ולעיתים הוא תופקד בעמדות שלא התאימו לו. בקיץ שלאחר מכן שמו קושר עם מעברים אפשריים לטורקיה או לסין, אך המגעים לא הבשילו לכדי מעבר. בניטס החליט לשמור על טיוטה כשחקן סגל, אך האחרון נכשל בביסוס מעמדו בהרכב, כשג'ונג'ו שלבי, ג'ק קולבק ואייזק היידן מועדפים כולם בהרכב על פניו. הוא ערך שלוש הופעות נוספות עבור המועדון: אחת בליגה בתיקו 1-1 נגד אסטון וילה, ושתי הופעות נוספות בשני משחקי הסיבוב השלישי של גביע ה-FA נגד ברמינגהאם סיטי.
בייג'ינג אנטרפרייזס.