בשנת 1973, אחרי שבקשתו לקבל ויזת יציאה לישראל נדחתה בגלל סיבות שהוגדרו "ביטחוניות", החל שרנסקי לעבוד כמתרגם עבור הפיזיקאי הנודע אנדריי סחרוב. בשנת 1974 נשא לאישה את אביטל (נטליה) שטיגליץ בבית הכנסת במוסקבה. בני הזוג לא קיבלו אישור עלייה, ואביטל עלתה לישראל לבדה מיד אחרי נישואיהם בתקווה שבעלה יקבל אישור לעלות בהמשך. שרנסקי הצטרף לארגון זכויות האדם קבוצת הלסינקי בראשותו של יורי אורלוב. הארגון, שהוקם בשנת 1976, נועד לפקח על יישום ולדווח על הפרות של הסכמי הלסינקי עליהם חתמה ברית המועצות ב-1975, ובהם סעיף המחייב שמירה על זכויות האדם. באותה העת, שרנסקי גם הפך לדובר העיקרי עבור אסירי ציון ומסורבי העלייה היהודים.
במרץ 1977 נעצר והוגש נגדו כתב אישום לפיו העביר למערב רשימה של 1300 שמות של מסורבי עלייה, שחלקם סורבו בשל החזקה בסודות מדינה, כפי שפורסם בניו יורק טיימס ב-1976. ביולי 1978 הרשיע אותו בית המשפט בבגידה, ריגול למען ארצות הברית, הסתה ותעמולה אנטי-סובייטית וגזר עליו 13 שנות מאסר. הוא ריצה 16 חודשים בכלא לֶפוֹרְטוֹבוֹ. על פי ספרו האוטוביוגרפי על התקופה "לא אירא רע", הצליח שרנסקי לשרוד את מחנות המעצר כיוון שבזכות דבקותו בזהותו היהודית ותשוקתו לעלות לישראל נשאר חופשי בנפשו. מסופר על כך שפעם ישב עם מספר סוהרים בחדר ואמר להם שהם כולם עבדים והוא היחיד באותו חדר שהוא אדם חופשי. שכן, כל הסוהרים נתונים לפקודותיהם של מפקדם ואין להם רצון חופשי כלל. ואילו לו יש חירות נפשית ומחשבתית. הוא יהודי ובנפשו הוא לא משועבד לאף אחד.
את שנות הישיבה בכלא העביר בין השאר באמצעות משחק ואימונים בשחמט, גם ללא לוח שחמט.
גם במאסר הוא לא הפסיק למחות, ונוספה לזה מחאה על תנאי מאסרו הקשים. הוא שבת רעב, במצטבר, כ-200 ימים.
במהלך שנותיו בכלא הפך שרנסקי לסמל המאבק על זכויות האדם בברית המועצות ומאבקה של היהדות שם.
שחרורו ועלייתו לישראל.
כבר בשנת 1978 התפרסמו ידיעות על כוונה להחליף את שרנסקי במרגלים סובייטיים, אך הדבר לא יצא אל הפועל.
בעקבות המאבק לשחרורו שאותו הובילה אשתו אביטל, ובעקבות לחץ דיפלומטי כבד מצד המערב, החליטה הכנסת לתבוע את שחרורו. ב-11 בפברואר 1986, לאחר שישב במאסר תשע שנים, שוחרר לבסוף שרנסקי במסגרת עסקה שבה נמסרו לברית המועצות חמישה מרגלים תמורת שלושה מרגלים מערביים, ביניהם שרנסקי. הסובייטים שיפרו מאוד את תנאי מאסרו בתקופה שלפני השחרור. הוא הבין שהוא עומד להשתחרר כשלראשונה, נתנו לו פירות טריים.
נשיא ארצות הברית רונלד רייגן דרש ששרנסקי ישוחרר שעה אחת לפני שני המרגלים האחרים בעסקה כדי להבדיל ביניהם, שהרי שרנסקי הואשם לשווא בריגול. דרישתו התקבלה, ושרנסקי שוחרר ראשון. החילופים בוצעו בגשר גליניקה שקישר בין גרמניה המזרחית למערבית. אפילו שם, שרנסקי התעקש לזלזל בברית המועצות ובניגוד להוראה שקיבל מהחייל ששחררו, לצעוד ישר - הוא חצה את הגשר בעקלתון. מיד לאחר חציית הגשר העניק לו שגריר ישראל בגרמניה את דרכונו הישראלי. בנמל התעופה בן-גוריון זכה לקבלת פנים נלהבת בהשתתפות ראש הממשלה שמעון פרס ושר החוץ יצחק שמיר.
בהגיעו לישראל ביקש שרנסקי להימנע מלקרוא לו אנטולי, אלא לכנותו בשמו העברי נתן, שבו הקפיד להשתמש בשנותיו הארוכות בכלא. במאי 1986 נסע שרנסקי עם אשתו לארצות הברית שם הוענקה לשניהם מדליית הזהב של הקונגרס, העיטור השני בחשיבותו בארצות-הברית כהוקרה על מאבקם למען זכויות האדם. ב-15 בדצמבר 2006 קיבל שרנסקי את מדליית החירות הנשיאותית של ארצות הברית מידי ג'ורג' בוש, והיה לישראלי הראשון (לפני שמעון פרס) ולאדם הלא-אמריקני הרביעי (אחרי נלסון מנדלה, האפיפיור יוחנן פאולוס השני, והאם תרזה) שקיבל את שני העיטורים האמריקניים החשובים ביותר של הנשיא והקונגרס - מדליית הזהב של הקונגרס ומדליית החירות הנשיאותית.
בשנת 1988 נבחר לעמוד בראש "הפורום הציוני", ארגון גג של מסורבי עלייה מברית המועצות. כמו כן, היה חבר מועצה של ארגון Peace Watch וכן עורך בג'רוזלם ריפורט.
בפוליטיקה הישראלית.
בעקבות העלייה הרוסית הגדולה בשנות ה-90 של המאה ה-20, הקים שרנסקי את מפלגת "ישראל בעלייה" שמטרתה הייתה לתת ביטוי לצורכיהם ומצוקותיהם של ציבור העולים מברית המועצות לשעבר. בבחירות לכנסת ה-14 (1996) התמודדה מפלגתו לראשונה, זכתה בשבעה מנדטים ושרנסקי כיהן כשר התעשייה והמסחר בממשלת נתניהו הראשונה. במסגרת תפקידו, חייב לסמן את מחיר המוצרים על ידי הדבקת מחיר עליהם. התקנה באה לבטל פטור שניתן לבתי עסק שלפיו מוצרים רבים היו פטורים מחובת הסימון. הצו שתוקן ביולי 1998 ביטל את רוב הפטורים.
בבחירות לכנסת ה-15 (1999) החליטה מפלגתו להתמקד בנושאים שהפריעו לציבור העולים (בעיקר קושי להינשא ברבנות והכרה ביהדותם של עולים חדשים). היעד שהציבו לעצמם היה לקבל את משרד הפנים שהיה בשליטת מפלגת ש"ס. הססמה שנבחרה הייתה - "מ.וו.ד. פאד ש"ס קונטרול ? ניאט. מ.וו.ד. פאד נאש קונטרול!" שתרגומה לעברית הוא "משרד הפנים בשליטת ש"ס? לא. משרד הפנים בשליטתנו!". סיסמה זו (שקוצרה לרוב ל"נאש קונטרול") הייתה סיסמת הבחירות המובילה של המפלגה וזכתה להדים רבים. בבחירות זכתה ישראל בעליה בשישה מנדטים ושרנסקי הצטרף לממשלת ברק כשר הפנים.
שרנסקי התפטר מתפקידו זה ביולי 2000 לפני ועידת קמפ דייוויד. בעקבות הבחירות המיוחדות לראשות הממשלה בהן נבחר אריאל שרון, הוא הצטרף לממשלתו וכיהן כסגן ראש הממשלה ושר הבינוי והשיכון.
בבחירות לכנסת ה-16 (2003) זכתה ישראל בעלייה בשני מנדטים בלבד (שרנסקי ויולי אדלשטיין). בעקבות הכישלון בבחירות (ירידה מ-6–7 מנדטים ל-2 בלבד) וקשיים כלכליים התמזגה המפלגה בתוך הליכוד. שרנסקי התפטר מהרשימה עוד בטרם הושבעה הכנסת ומונה לשר לענייני ירושלים, התפוצות והמאבק באנטישמיות.
ב-2 במאי 2005 התפטר מן הממשלה במחאה על תוכנית ההתנתקות.
בבחירות לכנסת ה-17 (2006) התמודד ברשימת הליכוד, בה הוצב במקום ה-11 לאחר הבחירות הפנימיות במרכז הליכוד, ונכנס לכנסת.
ב-11 באוקטובר 2006 הודיע על כוונה לפרוש מהחיים הפוליטיים. התפטרותו מהכנסת נכנסה לתוקף ב-21 בנובמבר ולאחר טקס פרידה בהשתתפות ראש הממשלה אהוד אולמרט.
פעילות ציבורית.
לאחר התפטרותו מהכנסת, עמד שרנסקי בראש מכון אדלסון למחקרים אסטרטגיים שבמרכז שלם בירושלים.
שימש כעמית במכון לאסטרטגיה ציונית וכחבר בפורום האסטרטגי בו.
ב-25 ביוני 2009 נבחר שרנסקי ליושב ראש הסוכנות היהודית כמועמד של ראש הממשלה בנימין נתניהו, הוא כיהן בתפקיד זה תשע שנים והוחלף בקיץ 2018 על ידי יצחק הרצוג.
בשנת 2019 זכה בפרס שומר ציון. בשנת 2020 זכה בפרס בראשית, המכונה ה"נובל היהודי".
דעותיו וספריו.
הסכסוך הישראלי-פלסטיני.
שרנסקי תומך במתן מדינה לפלסטינים על חלק משטחי יהודה, שומרון ועזה, אך רק בתנאי שהמדינה שיקימו תהיה מדינה חופשית עם שלטון דמוקרטי שתפסיק את ההסתה כנגד ישראל ותפרק את ארגוני הטרור. להסכמי אוסלו, שלטענתו נתנו לרשות הפלסטינית וליאסר ערפאת סמכויות ושטחים בלי לדרוש מהם מחויבות לדמוקרטיה, מלחמה בטרור ושמירה על זכויות אדם, הוא קרא "בגידה בעקרונות הדמוקרטיה".
לטענתו, לא יהיה שלום אמיתי עם מדינות ערב כי כל עוד כל עוד מדינות ערב הן דיקטטורות, יוכלו לעשות איתן שלום רק על בסיס של כוח.
בשנת 2010 פרסם נשיא ארצות הברית לשעבר, ביל קלינטון, את דעתו על המכשולים להסדר בישראל, ובראשם: העולים מברית המועצות. ייתכן שתרמה לדעתו זו שיחה שקיים עם נתן שרנסקי בשנת 2000, בזמן השיחות בקמפ דייוויד, שבה הוא שאל אותו מדוע הוא היה השר היחיד שהתנגד להסכם, ושרנסקי ענה: "אני לא יכול לתמוך בזה. אני רוסי. הגעתי מאחת המדינות הגדולות בעולם לאחת מהקטנות ביותר. אתה רוצה שאני אחלק אותה לשתיים? לא תודה!"
על להיות ישראלי.
שרנסקי אמר פעם: .
על הדמוקרטיה בעולם.
שרנסקי פרסם שלושה ספרים פרי עטו:
בספרו השני "טיעון בזכות הדמוקרטיה: כוחה של החירות לגבור על עריצות וטרור", שכתב עם רון דרמר ויצא ב-2004, מנסח שרנסקי את האידאולוגיה שלו בדבר חיוניותה של הדמוקרטיה לרווחתה, התקדמותה ושגשוגה של האנושות ואת הכרחיותה ליציבות, ביטחון וחירות ברחבי העולם. שרנסקי מחלק את העולם לחברות חופשיות ("free societies") וחברות-פחד ("fear societies"). בחברות חופשיות, (בתקופתנו - מדינות חופשיות) האדם חופשי ליזום ולבטא את היצירתיות שלו, וכך משיגה המדינה שגשוג כלכלי והתקדמות טכנולוגית, כמו כן - החירות מבטיחה שמירה על זכויות האדם, מניעת דיכוי ובקרה עצמית. לעומת זאת, בחברות הפחד, האזרחים מפחדים להביע את דעתם ומבצעים את מצוות השלטון בחוסר רצון, דבר הגורם להתפתחות איטית של הכלכלה, עוני ונחשלות טכנולוגית. משטר הפחד מפני השלטון מדכא יוזמה חופשית וביקורת על השלטון, ובכך פותח פתח לעריצות ושחיתות שמרקיבים את מנגנון המדינה.
כדי להבדיל בין חברת-פחד לבין חברה-חופשית שרנסקי מציע את "מבחן כיכר העיר"- אם אדם יכול לצעוד לכיכר העיר, ולבטא את דעותיו בלי שיחשוש ממעצר, מאסר או פגיעה, הרי שאדם זה חי בחברה חופשית, ולא בחברת פחד.