יהודה אליהו פעיל שנים רבות בתנועת ההתנחלות. הוא נחשב למקורבו ושותפו הפוליטי של בצלאל סמוטריץ'. בשנת 1999 היה ממקימי המאחז חרשה, שבו הוא מתגורר עד היום, ושימש במשך שבע שנים מזכיר המאחז. בשנת 2006 הקים יחד עם סמוטריץ' את תנועת רגבים ושימש המנכ"ל הראשון שלה. התנועה פועלת לקידום השתלטות ישראלית על קרקעות בגדה המערבית ולהגברת האכיפה נגד בנייה פלסטינית, בין היתר באמצעות עתירות ולחץ על רשויות המדינה. בהמשך שימש אליהו עוזר לראש המועצה האזורית מטה בנימין, רשות מקומית ישראלית שפועלת בגדה המערבית ומאגדת עשרות התנחלויות ומאחזים באזור רמאללה, ובין 2019 ל-2022 כיהן כמנכ"ל המועצה.

בפברואר 2023, לאחר שסמוטריץ' מונה לשר הנוסף במשרד הביטחון, אליהו מונה לעמוד בראש מינהלת ההתיישבות שהוקמה במשרד. המינוי למעשה הציב פעיל התנחלות ותיק בראש המנגנון האזרחי שהוקם כדי לממש את מדיניותו של סמוטריץ' בגדה המערבית. כראש המינהלת אליהו היה אחראי לקידום המדיניות בתחומי הקרקע, התכנון והבנייה, התשתיות, הכשרת המאחזים והאכיפה. בתקופת כהונתו הועברו סמכויות מידי המינהל האזרחי למנגנון הכפוף לסמוטריץ', הואצו הליכי התכנון בהתנחלויות, הוכשרו מאחזים, הורחבו הכרזות על אדמות מדינה והוגברה האכיפה נגד בנייה פלסטינית. ביולי 2025 אליהו הכריז כי מינהלת ההתיישבות השלימה את הכנת התשתית המקצועית הדרושה לסיפוח הגדה המערבית.

אליהו עצמו נהנה בעבר מהשיטות המפוקפקות המשמשות להקמה והרחבה של מאחזים. לפי תחקיר "הארץ", בשנת 2004 אליהו קיבל משכנתה עבור מגרש שנמצא בתוכנית המתאר של ההתנחלות נריה, אך ביתו נבנה בפועל בחרשה, שבאותה עת היה מאחז בלתי חוקי ללא תוכנית מתאר, על קרקע שמעמדה לא הוכשר. על פי התחקיר, המשכנתה ניתנה באמצעות מסמכים שסיפקה החטיבה להתיישבות, אף שלא היו לה זכויות בקרקע שעליה הוקם הבית.

במאי 2026 מונה אליהו למנהל רשות מקרקעי ישראל. בעקבות עתירות נגד הליך המינוי, שכללו טענות לפגמים ולניגודי עניינים הנובעים בין היתר מקרבתו לסמוטריץ', הממשלה הסכימה להצעת פשרה מצד בית המשפט וביטלה את המינוי והחזירה את הדיון לוועדת איתור בהרכב חדש. ביולי 2026 מונה אליהו לממלא מקום מנהל הרשות, אך בספטמבר זומן לשימוע לפני פיטורים בעקבות תלונות על תפקודו הניהולי והמקצועי. בעקבות התערבותו של ראש הממשלה בנימין נתניהו בוטלה הכוונה לפטרו, והוא נותר בתפקידו.

המסלול הפוליטי של אליהו, ממקימו של מאחז לא חוקי, דרך עבודתו בארגון רגבים, ועד לעמידה בראש מינהלת ממשלתית ורשות מקרקעי ישראל, ממחיש היטב את כוחה הפוליטי של תנועת ההתנחלות הישראלית וכניסתה למרכז מוקדי קבלת ההחלטות של מדינת ישראל. כשותפו הוותיק של סמוטריץ' וכמי שהופקד על ביצוע מדיניותו, אליהו מילא תפקיד מרכזי בהפיכת תוכנית סיפוח הגדה המערבית ממסגרת אידאולוגית למנגנון ממשלתי ולמדיניות המיושמת בפועל.