כניסה לחיים הפוליטיים
אדלשטיין היה אחד ממייסדי ומנהיגי מפלגת "ישראל בעלייה" (בראשות נתן שרנסקי) אשר כיוונה לציבור העולים ממדינות חבר העמים. המפלגה התמודדה לראשונה בבחירות לכנסת ה-14 (1996) וזכתה להישג מרשים – 7 מנדטים. "ישראל בעלייה" הצטרפה לקואליציה בראשות הליכוד ואדלשטיין מונה לשר לקליטת העלייה ב
ממשלה ה-27 בראשות
בנימין נתניהו.
במהלך כהונתו כשר לקליטת העלייה קיבלה מדינת ישראל מספר רב של עולים ממדינות חבר העמים. על-מנת להתמודד עם מספר העולים יזם אדלשטיין את הקמתם של מעונות לעולים וכן את הקמתו של שירות תעסוקה ייחודי לאוכלוסיית העולים.
בבחירות לכנסת ה-15 (1999) זכתה "ישראל בעלייה" ב-6 מנדטים ואדלשטיין המשיך בכהונתו כח"כ. במהלך כהונת הכנסת ה-15 שימש לסירוגין הן כסגן יו"ר הכנסת וכיו"ר סיעתו בכנסת והן כסגן השר לקליטת העלייה (2001 – 2003) בממשלתו של
אריאל שרון. כמו-כן היה חבר בוועדות הכנסת הבאות: הכנסת, חוקה חוק ומשפט, חינוך, עלייה וקליטה, הוועדה לקידום מעמד האישה ועוד.
מעבר לליכוד
בבחירות לכנסת ה-16 זכתה "ישראל בעלייה" ב-2 מנדטים בלבד. לאחר הבחירות עברו שני חברי הסיעה, אדלשטיין ושרנסקי, אל סיעת הליכוד. כיהן כסגן יו"ר הכנסת מטעם סיעת הליכוד. בבחירות לכנסת ה-17 (2006) שובץ במקום ה-15 ברשימת הליכוד שהתברר כלא ריאלי. שנה לאחר כן עם התפטרותם של שני ח"כ מסיעת הליכוד, שב אדלשטיין לכנסת.
לקראת הבחירות לכנסת ה-18 (2009) שובץ אדלשטיין במקום ה-12 ברשימת הליכוד ונכלל בסיעת הליכוד בכנסת זו. מונה לשר ההסברה והתפוצות ולשר הממונה על רשות השידור בממשלה ה-32 בראשות בנימין נתניהו. ב-2010 התפטר מתפקידו כשר הממונה על רשות השידור.
יו"ר הכנסת
בכנסת ה-19 (2013) נבחר אדלשטיין לתפקיד יו"ר הכנסת. בזכות הישגיו בבחירות המקדימות שובץ במקום השלישי ברשימת הליכוד בבחירות לכנסת ה-20 (2015). עם השבעת הכנסת ה-20 נבחר בשנית לכהן כיו"ר הכנסת.
בתפקידו כיו"ר הכנסת השמיע אדלשטיין לא פעם ביקורת נגד התנהגות לא אתית של חברי כנסת, ממפלגות שונות, בהן גם מפלגתו שלו. מנגד הושמעה נגדו מספר פעמים ביקורת תקשורתית ופוליטית בטענה כי החלטותיו ודבריו חורגים לעתים מן הממלכתיות הנדרשת מיו"ר הכנסת ומכוונים לטובת עמדותיו הפוליטיות ומפלגתו הליכוד. בין היתר נטען כך כאשר פסל שאלות שהופנו כלפי רה"מ נתניהו במליאת הכנסת ונגעו בפרשיות במסגרתן נחקר נתניהו במשטרה. בהקשר אחר ספג אדלשטיין ביקורת ציבורית סביב סנקציות שננקטו נגד עוזרות פרלמנטריות בכנסת בשל מה שהוגדר כחריגה מקוד הלבוש.