בינואר 2003, בטיסטה הצטרף לטריפל H, ריק פלייר ורנדי אורטון וביחד הם יצרו את הקבוצה "אבולוציה", אך באותו זמן בטיסטה קרע את שריר הזרוע התלת-ראשי שלו ודבר זה חייב אותו לצאת לתקופת החלמה. לאחר תקופת החלמה בת 8 חודשים, בטיסטה חזר ב-20 באוקטובר בפרק של Raw, שם התערב במהלך קרב בין גולדברג לשון מייקלס, ואז שבר לגולדברג את העקב עם כיסא. לאחר מכן, חבריו של בטיסטה ל"אבולוציה" באו והעניקו לו 100,000 דולר על כך שפצע את גולדברג. ב-10 בנובמבר, גולדברג ניצח את בטיסטה בפסילה לאחר התערבות של טריפל H.
באירוע "ארמגדון", בטיסטה השתתף בשני קרבות: בראשון הוא הפסיד לשון מייקלס, אך בשני ניצח, יחד עם ריק פלייר, בקרב זוגות מרובה משתתפים כדי לזכות בתוארי הזוגות. באותו הערב, אורטון גם זכה באליפות הבין יבשתית וטריפל H זכה באליפות העולם במשקל כבד, כך שאבולוציה החזיקה בכל התארים החשובים של התוכנית. בטיסטה ופלייר המשיכו להחזיק בתארים עד 16 בפברואר שם הפסידו אותם לבוקר טי ורוב ואן דאם. הם זכו בתואר שוב והחזיקו בו לתקופה קצרה.
באירוע "סדרת ההישרדות", טריפל H, בטיסטה, אדג' וסניצקי הובסו בידי מייבן, כריס ג'ריקו, כריס בנואה ורנדי אורטון, ולפי תנאי הקרב, כל אחד מחברי הצוות המנצח היה יכול לשלוט בתוכנית Raw ליום. מערכת היחסים בין בטיסטה לטריפל H התחילה להתערער. לאחר הפסד לג'ריקו, טריפל H צחק על באטיסטה והעליב אותו. באותו יום טריפל H נמצא מעולף מאחורי הקלעים, ולפי דבריו של פלייר, בטיסטה תקף אותו. אך מאוחר יותר התברר כי טריפל H ובטיסטה העמידו פנים כדי למנוע מטריפל H להילחם בקרב מאוחר יותר. במהלך השבועות הבאים, האהדה לבטיסטה החלה לגדול והוא התחיל להתעמת יותר עם דמויות "רעות". אך הוא המשיך לעזור לטריפל H.
כששנת 2005 החלה, טריפל H חשש שבטיסטה ייקח ממנו את תואר העולם, והציע לבטיסטה לא להיכנס לקרב הרויאל ראמבל, שהזוכה בו יכול לקבל קרב על תואר העולם, ובמקום זאת יתרכז בלעזור לטריפל H להגן על תארו. בטיסטה נכנס למרות הכל ואף ניצח וקיבל זכות לקרב על תואר העולם ברסלמניה 21. לבטיסטה ניתנה הבחירה: להילחם מול טריפל H על תואר העולם או מול אלוף ה-WWE, ג'ון "בראדשו" לייפילד (JBL). טריפל H הציע לבטיסטה לאתגר את לייפילד כדי שהקבוצה שלהם תוכל "לשלוט בארגון". במהלך אותו זמן, בטיסטה כמעט נדרס מהלימוזינה של JBL. בטיסטה התעמת עם JBL בכמה מקרים ו-JBL הכחיש שהוא נהג בלימוזינה. בטיסטה שמע שיחה בין ריק פלייר וטריפל H, וגילה שהם ביימו את הדריסה כדי שבטיסטה לא ילחם מול טריפל H. בטיסטה העמיד פנים שהוא כן עובר לסמאקדאון, כשהוא מסמל לחבריו באגודל מורם שהוא עובר לשם, אך אז בטיסטה הפך את האגודל שלו כלפי מטה, תקף את פלייר ואת טריפל H והעביר את טריפל H דרך שולחן, ואז הכריז שהוא ילחם מול טריפל H, וכך הפך לדמות "טובה".
סמאקדאון (2008-2005).
בטיסטה זכה באליפות העולם מטריפל H ב-3 באפריל 2005 ברסלמניה 21. באטיסטה גם הגן על תארו בקרב חוזר מול טריפל H באירוע באקלאש. לאחר שהגן על תוארו מול אדג', ריק פלייר וטריפל H תקפו את בטיסטה כשטריפל H מאתגר אותו לקרב "גיהנום בכלוב" על התואר באירוע "נקמה". בטיסטה אכן ניצח את טריפל H ושמר על התואר, ובכך נהיה המתאבק הראשון שניצח אותו בסוג הקרב הזה.
דמותו של בטיסטה עברה לתוכנית סמאקדאון ב-30 ביוני. בטיסטה החל במהרה יריבות מול JBL .JBL ניצח את בטיסטה בפסילה באירוע "המסיבה האמריקנית הגדולה" לאחר שבטיסטה השתמש בכיסא ברזל על JBL. ב"סאמרסלאם" הוא ניצח את JBL בקרב ללא חוקים, ולאחר מכן ניצח אותו בקרב רצועה בסמאקדאון. בטיסטה צוות עם המתאבק אדי גאררו והשניים הוצגו כחברים טובים שעזרו זה לזה, למרות שנאמנותו של גאררו הוטלה בספק. בטיסטה ניצח אותו באירוע "ללא רחמים". לאחר שבטיסטה סבל מקרע בשריר הגב שלו בנובמבר, הוכרז שילחם בקרב על התואר מול אדי גאררו ורנדי אורטון כעבור שבוע, כשהתוכניות היו שגאררו יזכה בתואר ובאטיסטה יצא לחופשת החלמה. אך גאררו נפטר ביום של הקרב, ודמותו של בטיסטה הספידה אותו.
בטיסטה הוביל את צוות סמאקדאון לניצחון על צוות Raw ב"סדרת ההישרדות" 2005. במהלך התוכניות לפני הקרב, כדי להסביר את פציעתו של בטיסטה, קיין והביג שואו תקפו אותו. לאחר שעזר לדמותו של ריי מיסטריו, שגם הנציח את גאררו, מול ביג שואו וקיין, הוכרז ששני הצוותים יפגשו בארמגדון.
ממש לפני הקרב, בטיסטה ומיסטריו ניצחו את "MNM" וזכו בתוארי הזוגות. הקרב שלהם מול ביג שואו וקיין הפך לקרב של אלופי זוגות מול אלופי זוגות. בטיסטה ומיסטריו הפסידו להם. כעבור שבועיים, הם הפסידו את התארים בחזרה ל-MNM לאחר שמארק הנרי תקף את בטיסטה. כעבור שבוע, שני הצוותים נפגשו שוב בקרב כלוב ברזל, שם הנרי שוב תקף את בטיסטה וגרם להפסד שלו ושל מיסטריו. כעבור 3 ימים, ב-9 בינואר, הוכרז שבטיסטה שוב קרע את השריר התלת ראשי. ב-13 בינואר, הוא ויתר על תואר העולם למשקל כבד. בטיסטה החזיק בתואר 282 ימים, יותר מ-280 הימים שהחזיק בו טריפל H. לפיכך בטיסטה שבר את השיא של כל מתאבק אחר שהחזיק בתואר זה.
חזרה מפציעה (2006).
בטיסטה הופיע בכמה אירועים, כשהיה פצוע, ובכולם אמר שהוא מתכוון לזכות בתואר שוב. באטיסטה חזר ב-7 ביולי ומיד איתגר את מארק הנרי לקרב. בטיסטה גם ניצח, יחד עם ריי מיסטריו ובובי לאשלי, את בוקר טי, פינלי ומארק הנרי. הנרי נפצע בקרב זה וכך הקרב ביניהם נדחה.
מכיוון שהקרב בינו ובין הנרי ב"מסיבה האמריקנית הגדולה", בו המנצח מקבל קרב על התואר, בוטל, בטיסטה איתגר כל מתאבק להילחם מולו. לאתגר ענה מר קנדי. בטיסטה הפסיד בקרב זה בפסילה. לאחר מכן הפסיד לקנדי עוד קרב בספירת חוץ ובסוף ניצח אותו בהצמדה.
באותו הזמן, בטיסטה ניסה לזכות שוב בתואר העולם, והוא התחיל יריבות עם המלך בוקר. בטיסטה זכה בקרב ביניהם ב"סאמרסלאם" בפסילה, אך לא בתואר. כעבור כמה שבועות בסמאקדאון, בטיסטה שוב הפסיד לבוקר לאחר שבוקר קיבל עזרה מכמה מתאבקים אחרים. בטיסטה המשיך להילחם מול בוקר ולבסוף ניצח אותו ב"סדרת ההישרדות", שנערכה, באופן אירוני, במקום בו הוא ויתר על התואר בינואר.
אליפות העולם (2007).
ברסלמניה 23, בטיסטה הפסיד את התואר לקברן. הם המשיכו להילחם על התואר, ולאחר קרב שהסתיים בתיקו, הם נלחמו בקרב כלוב ברזל שגם הסתיים בתיקו. לאחר קרב הכלוב, אדג' זכה בתואר העולמי מהקברן. בטיסטה נלחם מול אדג' על התואר ב"יום הדין", ב"לילה חד פעמי" (בקרב כלוב) וב"ליל האלופים", אך הפסיד. ההפסד בקרב השלישי מנע מבטיסטה לקבל קרב על התואר כל עוד אדג' הוא אלוף.
בטיסטה היה אמור להילחם מול קאלי הגדול במסיבה האמריקנית הגדולה, אך תוכניות אלה השתנו שבוע לפני הקרב: אדג' ויתר על תארו. נערך קרב גדול על התואר באותו יום שם קאלי זכה בתואר לאחר שהוא מדיח את בטיסטה ואת קיין, שהיה אמור לקבל קרב על התואר. כעבור יומיים, בטיסטה וקיין הפסידו לקאלי בקרב על התואר. בטיסטה ניצח את קאלי בפסילה ב"סאמרסלאם" ובאירוע "בלתי נסלח", ניצח את קאלי ואת ריי מיסטריו וזכה בתואר בפעם השלישית. כעבור חודש הוא ניצח את קאלי והגן על תארו.
לאחר חזרתו של הקברן, בטיסטה איתגר אותו לקרב וניצח את אותו ב"סייבר סאנדיי". ב"סדרת ההישרדות", הם נלחמו בקרב "גיהנום בכלוב" שם בטיסטה ניצח כתוצאה מהתערבות של אדג' החוזר. ב"ארמגדון", אדג' ניצח את הקברן ואת בטיסטה וזכה בתואר.
חזרה ל-Raw.
בטיסטה המשיך לנסות לקבל קרב על התואר, כשהוא נלחם ברויאל ראמבל ובקרב "תא ההדחות" כדי לקבל קרב על התואר. הוא הפסיד בשני הקרבות.
ברסלמניה 24, הוא ניצח את אומאגה. לאחר ששון מייקלס הפריש את ריק פלייר באותו אירוע, ולאחר שבדראפט 2008 של הארגון, נקבע שבטיסטה יעבור לתוכנית Raw, בטיסטה החל יריבות מול מייקלס, כשהוא מפסיד לו בבאקלאש בקרב בו כריס ג'ריקו היה השופט. לאחר מכן בטיסטה ניצח את מייקלס בקרב אלונקה.
בטיסטה זכה באליפות הזוגות יחד עם ג'ון סינה, אך הם הפסידו את התארים חזרה לקודי רודס ולטד דיביאסי הבן כעבור שבוע. ב"סאמרסלאם", בטיסטה ניצח את סינה.
ב-26 באוקטובר, בטיסטה זכה בתואר העולמי הרביעי שלו כשניצח את כריס ג'ריקו בקרב שבו סטיב אוסטין שפט. אך כעבור 8 ימים, הוא הפסיד לג'ריקו את התואר בקרב כלוב.
לאחר מכן בטיסטה החל יריבות מול רנדי אורטון. הצוות שלו (שכלל את CM פאנק, קופי קינגסטון, מאט הארדי ו-R טרות') הובס ב"סדרת ההישרדות" בידי הצוות של אורטון (שכלל את אורטון עצמו, קודי רודס, שלטון בנג'מין, מארק הנרי ואת ויליאם ריגל). כעבור חודש, ב"ארמגדון", בטיסטה ניצח את אורטון. למחרת היום, במהלך קרב, אורטון בעט לבטיסטה בראש, דבר ש"פצע" אותו.
בטיסטה חזר ב-6 באפריל והציל את טריפל H, שיין מקמהן ווינס מקמהן מרנדי אורטון, קודי רודס וטד דיביאסי הבן. וינס מקמהן הכריז שבטיסטה, שיין מקמהן וטריפל H ילחמו בבאקלאש מול אורטון, רודס ודיביאסי, בקרב שבו אם הצוות של אורטון ינצח, הוא יזכה בתואר ה-WWE. הצוות של אורטון ניצח. למחרת היום, בטיסטה ניצח את ביג שואו וקיבל קרב על התואר מול אורטון ב"יום הדין". הוא הפסיד לו, אבל זכה בתואר ה-WWE כעבור חודש בקרב כלוב. למחרת היום בטיסטה הוכרח לפנות את תארו כי הצוות של אורטון פצע אותו.
בתוכנית Raw של ה-14 בספטמבר, בטיסטה הגיע לזירה ואמר שיש לו הודעה שתשפיע על הקריירה שלו. אורטון יצא אל הזירה והניח שבטיסטה מתכוון לפרוש, אך בטיסטה אז הוריד את הגבס מידו ותקף את אורטון, ואז הכריז שהוא עובר לסמאקדאון. מאוחר יותר באותו לילה, הוא ניצח את אורטון.
חזרה מפציעה (2010-2009).