בפברואר 1986, לאחר תשע שנות מאסר בתנאים קשים, ולאחר מאבק עיקש שלו ושל אשתו, שוחרר בעסקת חילופי מרגלים, שבה הוחזרו לברית-המועצות חמישה מרגלים תמורת שלושה מרגלים גרמנים ושרנסקי – אף-על-פי שמעולם לא עסק בריגול. במאי 1986 יצאו שרנסקי ואשתו לארצות-הברית. במאי 1988 הקים את הפורום הציוני, על בסיס מרכז המידע של אסיר ציון לשעבר יוסף מנדלביץ', בציפייה לגל עלייה חדש מברית-המועצות. בינואר 1993 קיים הפורום את ועידתו הראשונה בהשתתפות יותר מ-1,000 צירים. הפורום העניק הלוואות ורשת של שירותים שונים לעולים.

שרנסקי כיהן כחבר הכנסת מהכנסת ה-14 (1996) עד הכנסת ה-17 (2006). בבחירות לכנסת ה-13 (1992) סירב שרנסקי להצטרף למפלגת העולים ד"ע (דמוקרטיה-עלייה), וכינה אותה מפלגה עדתית. לקראת הבחירות לכנסת ה-14 (1996) שינה את טעמו, והקים את תנועת ישראל בעלייה, שנרשמה כמפלגה. בבחירות ביוני 1996 זכתה המפלגה ל-7 מנדטים והצטרפה לקואליציה שהקים בנימין נתניהו. שרנסקי התמנה לשר התעשייה והמסחר. לאחר הבחירות לכנסת ה-15 (2000) כיהן כשר הפנים, אך התפטר מהממשלה לפני ועידת קמפ-דייוויד. ב-2001, לאחר היבחרו של אריאל שרון לראש הממשלה, נתמנה שרנסקי לשר הבינוי והשיכון ולסגן ראש הממשלה. לאחר הבחירות לכנסת ה-16 (2002) התמזגה מפלגת ישראל בעלייה עם הליכוד. שרנסקי התפטר מהכנסת וכיהן כשר ללא תיק; ב-2005 התפטר מהממשלה על רקע תוכנית ההתנתקות. שרנסקי נבחר מטעם הליכוד לכנסת ה-17 (2006) אך כמה חודשים לאחר מכן הגיש את התפטרותו מן הכנסת ופנה לעסוק במחקר. שרנסקי נחשב נץ בדעותיו, אף-על-פי שאינו מרבה להתבטא בפומבי בנושאים מדיניים.

ב-1986 קיבל שרנסקי מידי נשיא ארצות-הברית רונלד רייגן את "מדליית הזהב של הקונגרס" – העיטור השני בחשיבותו בארצות-הברית – בשל מלחמתו למען זכויות אדם בברית-המועצות; בדצמבר 2006 קיבל מנשיא ארצות-הברית ג'ורג' בוש את "מדליית החירות הנשיאותית" – העיטור הראשון בחשיבותו בארצות-הברית.