בשנת 1984 נבחר לראשונה לכנסת ברשימת הליכוד[4], ושימש בין היתר כמשקיף הכנסת למועצת אירופה וחבר המשלחת הישראלית לועידת מדריד ב-1991. כיהן כיו"ר ועדת המשנה לתקציב הביטחון (בכנסת ה-12), כיו"ר ועדת החוץ והביטחון (בכנסת ה-14) וכיו"ר הוועדה לביקורת המדינה (בכנסת ה-15).
בשנת 2001 מינהו אריאל שרון לשר לביטחון הפנים, תפקיד בו כיהן עד 2003. בתקופת כהונתו נאלצה המשטרה להתמודד עם פיגועי הטרור הקשים שהתחוללו בארץ במסגרת האינתיפאדה השנייה ובמחסור של כוח אדם במשטרה. ב-2003 מונה לשר בלי תיק במשרד ראש הממשלה. באותה השנה, כאשר התפרסמה תוכנית ההתנתקות, הוביל את ההתנגדות לתוכנית בליכוד ויצר חזית משותפת עם עוד ח"כים מהליכוד ("מורדי הליכוד") למניעת מימושה, כולל הצבעה נגדה בכנסת. כתגובה פיטר אותו שרון מהממשלה ב-26 באוקטובר2004.
בשנת 2005 הציג לנדאו את מועמדותו לראשות הליכוד, במקביל לבנימין נתניהו, שאול מופז, סילבן שלום, משה פייגלין וישראל כ"ץ, כאלטרנטיבה ימנית. בעצתו של שמואל חייק הודיע לנדאו על פרישתו מההתמודדות, ותמך במועמד בנימין נתניהו.
בבחירות לכנסת ה-17 הוצב לנדאו במקום ה-14 ברשימת הליכוד, ולא נבחר לכנסת עקב זכיית המפלגה ב-12 מנדטים בלבד. בפברואר 2007, עם התפטרותו של דני נוה מהכנסת, היה לנדאו אמור להיכנס לכנסת על פי מיקומו ברשימה, אך ויתר.
בנובמבר 2008 הודיע על עזיבתו את הליכוד, ומעברו למפלגת ישראל ביתנו. הוא הוצב על ידי אביגדור ליברמן במקום השני ברשימה, נבחר לכנסת ה-18 וב-31 במרץ2009 מונה לשר התשתיות הלאומיות, תפקיד ששמו שונה בתקופת כהונתו לשר האנרגיה והמים. בתפקידו זה התנגד ליישום מסקנות ועדת ששינסקי להעלאת נטל המס על הפקת נפט וגז טבעי בישראל[5].
בשנת 2011, במסגרת דיון בכנסת בחוקים שנועדו לשנות את פני בית המשפט העליון, מתח לנדאו ביקורת חריפה על בית המשפט העליון: "אין בהרכב שופטי בית המשפט העליון פלורליזם, אלא יש בו אליטיסטיותאשכנזית. הוא שמאלני, פוליטי, מנותק מיהדות ולעיתים מהמציאות, ומרשה לעצמו לפלוש לתחומים לא לו"[6].