אנטולי שרנסקי החל לפעול בנושאי זכויות אדם לאחר הפלישה הסובייטית לפראג ב-1968. שנות ה-70 הפך לפעיל בולט בתנועה הציונית בברית המועצות.
במרץ 1977 נעצר והורשע בבגידה וריגול, ונידון ל-13 שנות מאסר, בבידוד ועבודות כפיה. במהלך מאסרו שבת רעב תקופה ארוכה במחאה על שלילת זכויותיו, ביניהן קבלת מכתבים ומבקרים.
בעת מאסרו ניהלה אשתו אביטל, שגורשה מברית המועצות לאחר נישואיהם, מערכה בינלאומית לשחרורו, שנשאה פרי בפברואר 1986, עת שוחרר שרנסקי מהכלא ועלה לישראל.
לאחר קליטתו המשיך שרנסקי להיאבק למען פתיחת שערי העליה ליהודי ברית המועצות. ב-1995 הקים את מפלגת "ישראל בעליה". ב-1996 נבחר לכנסת מטעמה ומונה לשר התעשיה והמסחר. ב-1999 מונה לשר הפנים. ב-2000 התפטר מהממשלה עקב חילוקי דיעות מדיניים עם ראש הממשלה דאז אהוד ברק.
במרץ 2001 מונה לשר הבינוי והשיכון.
שרנסקי נשוי ואב לשניים.