כאדם צעיר המשיך בפעילות פוליטית במסגרת מפלגת
חד"ש. בשנים 2003-1998 כיהן כחבר מועצת העיר חיפה מטעם חד"ש. במהלך כהונתו הוביל מאבק למתן הכרה לתרבות ולמורשת הערבית בעיר, בין היתר על ידי מתן שמות ערביים לשכונות בחיפה בהן רוב התושבים הם ערבים. בשנים 2003-2000 כיהן חבר בוועד הנהלת תיאטרון ”אלמידאן” בחיפה. השתתף בהפגנות במגזר הערבי במסגרת אירועי אוקטובר 2000.
בשנים 2006-2003 עבד כמנהל מיזמים בעמותת "סיכוי - לקידום שוויון אזרחי", עמותה הפועלת להגברת השוויון בין יהודים וערבים בישראל. בשנת 2006 מונה לתפקיד מזכיר מפלגת חד"ש. בבחירות לכנסת ה-19 (2013) שובץ במקום השישי ברשימת חד"ש, שהתברר לאחר הבחירות כלא ריאלי.
במסגרת פעילותו הפוליטית היה עודה ממובילי המאבק הציבורי למען הכרה ממשלתית בישובים הבדואים הלא-מוכרים בנגב וכן ממובילי המאבק נגד יוזמות המדינה לגיוס צעירים ערבים לשירות צבאי ושירות לאומי. החל בשנת 2015 מכהן כחבר בדירקטוריון "קרן דרוויש".
יו"ר הרשימה המשותפת
לקראת הבחירות לכנסת ה-20 (2015) התמודד עודה בבחירות המקדימות לראשות חד"ש וניצח את יריבו - עו"ד סאמח עיראקי (427 קולות מול 302 קולות). העלאת אחוז החסימה ל-3.25% בבחירות לכנסת, אשר נועדה בין היתר לפגוע במפלגות הערביות, גרמה לשלוש המפלגות הערביות הגדולות (חד"ש, בל"ד, רע"ם-תע"ל) להתמודד בבחירות ברשימה אחת – הרשימה המשותפת. במסגרת ההסכם בין המפלגות נקבע כי עודה ישובץ בראש הרשימה ויכהן כיו"ר הרשימה המשותפת. לפני הבחירות סירבה הרשימה המשותפת לחתום על הסכם עודפים עם רשימת מרצ, מהלך שזכה לביקורת פוליטית מצד השמאל הציוני. לאחר הבחירות הצהיר עודה כי ההחלטה לסרב להסכם הייתה שגויה.
בבחירות לכנסת ה-20 זכתה הרשימה המשותפת ב-13 מנדטים ועודה הושבע כחבר כנסת. במהלך כהונתו היה חבר בוועדת הכנסת, חבר בוועדת העבודה, הרווחה והבריאות, וכן כיהן כיו"ר שדולת התרבות וכחבר בשדולה לחיזוק ולפיתוח הכלכלה הערבית.
מבין חברי סיעת הרשימה המשותפת נחשב עודה למוביל קו מתון בנוגע ליחסי המגזר הערבי ומדינת ישראל (קו התואם את אידיאולוגיית מפלגת חד"ש). כהונתו כיו"ר הרשימה המשותפת כוללת מחד-גיסא ניסיונות לנהל מו"מ מול הממשלה על מנת להשיג הטבות כלכליות וחברתיות למגזר הערבי ומאידך-גיסא מתאפיינת במפגני מחאה והתבטאויות נגד מדיניות הממשלה בנושאים מדיניים וחברתיים. חלק מאותן התבטאויות זיכו אותו בביקורת חריפה מצד פוליטיקאים במפלגות הימין והמרכז. כך למשל היה עודה שותף לדיונים שהובילו לגיבוש תוכנית חומש ממשלתית המבטיחה תקצוב ייעודי לישובים ערביים בתקציב המדינה, מנגד הוביל את החלטת הרשימה המשותפת להיעדר מהלווייתו של נשיא המדינה שמעון פרס והאשים את ח"כ וראש השב"כ לשעבר אבי דיכטר ברצח מנהיגים פלסטיניים (על כך ננזף על ידי ועדת האתיקה של הכנסת).
בינואר 2017 הגיעו כוחות משטרה לכפר הבדואי אום אל חיראן (אחד הישובים הבלתי מוכרים בנגב) על מנת לממש צו שיפוטי ולפנות את התושבים מבתיהם. עודה, אשר נכח במקום על מנת למחות על הפינוי, נפגע בראשו במהלך עימות בין התושבים המפונים וכוחות המשטרה. גורם הפגיעה כמו גם כלל העובדות סביב אירועי אותו יום שנויים במחלוקת. על פי עדותו, נורה בראשו בקליע ספוג ורוסס בגז פלפל על ידי השוטרים. מנגד, טענה המשטרה שלפגיעה בו גרמה אבן אותה זרק אחד המפגינים הבדואים.