蘇哈托在其長達32年的統治中，由於擔心前總統蘇加諾的家人會重返政壇，所以禁止蘇加諾家族的人從政。他對蘇加諾的兒子進行了多方鉗製，迫使他們遠離政治。可蘇哈托偏偏忽略了蘇加諾的女兒們。由於家道中落和父親的慘死，蘇加諾的子女們曾一度發誓不再涉足政壇。梅加瓦蒂因此度過了她一生中最失意的20年。
但她並沒有因為父親的下台和悲慘遭遇而疏遠政治。雖然在蘇哈推翻了蘇加諾政府的蘇哈托托執政時期，她很難在政壇上露麵，但還是十分關心國內外大事。她時常到印尼各地進行考察，了解基層組織的情況。20世紀70年代，她還在丈夫的陪同下專門到歐洲一些國家考察了那裏的政治體製。這些，都為她日後的政治複出奠定了堅實的基礎。1975年印尼民主黨成立以後，黨內派係紛爭不斷。1982年，當時民主黨的總主席蘇爾亞迪想到了這個黨的創始人蘇加諾的女兒、得到群眾廣泛愛戴的梅加瓦蒂，希望借助她的影響力平息黨內紛爭。1987年大選前，蘇爾亞迪設法說服她擔任了印尼民主黨雅加達中央分會主席。梅加瓦蒂的參政，使人們將對蘇加諾的緬懷之情轉移到了他女兒身上。在中爪哇的競選活動中，隻要梅加瓦蒂一露麵，群眾就會踴躍地前往助威，使民主黨在當年的大選中一舉奪得40個席位。梅加瓦蒂與她的丈夫陶菲克·基瑪斯雙雙當選國會議員，成為當時惟一的一對夫妻議員。1993年12月，這位開國總統的女兒終於成為其父開創的印尼民主黨的總主席。這標誌著蘇加諾家族東山再起，也引起了蘇哈托的警覺。為了防止競爭對手的形成，他直接插手印尼民主黨的事務。在政府的壓力下，印尼民主黨1996年6月召開特別會議，強行將梅加瓦蒂擠出領導機構。這個舉動引發了廣大民主黨員和群眾的強烈不滿，並進而引發了一個月以後發生在雅加達的20年來最激烈的騷亂。這場嚴重流血衝突共造成100多人傷亡，其中大部分是梅加瓦蒂的支持者。1998年5月，蘇哈托在執政32年後辭職，梅加瓦蒂的支持者奪回了各地的分部。同年10月，梅加瓦蒂率領她的支持者從印尼民主黨中脫離出來，組建印尼民主鬥爭黨，並自任主席。在1999年6月舉行的議會大選中，梅加瓦蒂領導的印尼民主鬥爭黨提出了比較穩妥和務實的政治和經濟綱領。在各地分裂傾向有所抬頭時，該黨堅持國家統一，反對聯邦製；在處理蘇哈托及其家族斂財聚富等問題上，主張通過法律手段解決；在最敏感的軍隊雙重職能問題上，提出逐步削弱軍隊擔負的政治社會責任；在經濟發展上，主張加強農業、種植業、海洋捕撈業和旅遊業，從而以較小的投入換取更多的就業機會。這些主張受到廣大中下層人民的擁護和歡迎。競選期間，無數支持者身著紅色黨服，舉著以“雄牛”為標誌的民主鬥爭黨的紅旗，把各大城市變成了“紅色海洋”。
在人民高漲情緒的支持下，印尼民主鬥爭黨在參選的48個政黨中獲得了33.73%的選票、154個議席，成為新議會中第一大黨，梅加瓦蒂被該黨一致推舉為未來的總統候選人。當地輿論稱民主鬥爭黨為“人民的政黨”。人民普遍寄希望於這個曾經遭受迫害的政黨，希望梅加瓦蒂領導他們革故鼎新，開創新時代。印尼民主鬥爭黨在大選中的勝利引起了當時執政的專業集團黨的高度警惕。該黨領導人先後會見了民族覺醒黨、國家使命黨等數個大黨的負責人，試圖與他們聯合，戰勝民主鬥爭黨。另外，幾個穆斯林政黨還提出了女人不能在穆斯林國家當總統的問題。梅加瓦蒂通過媒體有力地反駁了這些過時的說法，並組成了幾個工作隊，分別與政界、軍界、宗教界保持接觸。支持民主鬥爭黨的學術、宗教團體，知名人士及廣大公眾開始站出來為梅加瓦蒂鳴不平。他們指出，在穆斯林國家巴基斯坦和孟加拉，早已有女總理上台執政，印尼為什麼就不能有女總統？
甚至有1000多名梅加瓦蒂的支持者還咬破手指按手印，開展“血印運動”，誓死支持梅加瓦蒂。另一方麵，在國會中擁有38個議席的軍方對民主鬥爭黨態度也比較友善。大選後不久，印尼武裝部隊司令發表講話，要求人們接受大選結果。軍隊中其他高級將領也表示，軍隊將接受人民的選擇，“不論是男性還是女性”，隻要是國家最優秀的兒女就行。在一些保守的穆斯林組織反對由女性擔任總統的時候，軍方的態度對梅加瓦蒂無疑是有力的支持。但隨著“人協”選舉日期臨近，爭奪總統寶座的大戰愈演愈烈，梅加瓦蒂開局十分不利，在10月3日和6日人民協商會議主席和人民代表會議（國家立法機構）議長的爭奪戰中連連失利。瓦希德宣布國家進入緊急狀態由改革派、民族主義黨和幾個穆斯林小集團組成的“中軸集團”意外地聯合起來，支持在議會中僅有35個議席的國家使命黨主席賴斯奪取了“人協”主席桂冠。緊接著，人民代表會議議長職位又被專業集團黨總主席丹戎占據。這兩個出人意料的結果使得在國會中贏得154個議席的第一大黨——民主鬥爭黨受到排斥，引起其支持者的強烈不滿。在問鼎總統寶座最後衝刺階段中，梅加瓦蒂過分相信政治盟友對她的承諾，對如何排除議會交替中遇到的障礙，沒有果斷處置。在關鍵時刻，梅加瓦蒂沒能在穆斯林政黨中贏得支持，這些政黨錯誤地把她當做是非宗教主義者，與印尼的基督教少數派關係密切，加上民主鬥爭黨在“人協”中建立必要的聯盟方麵行動緩慢又動手較晚，致使她在10月20日的總統選舉中，最終以60張選票之差輸給了伊斯蘭教師聯合會主席瓦希德，隻能屈就副總統一職。梅加瓦蒂辛辛苦苦地籌劃、準備、行動，反而為瓦希德做了“嫁衣裳”。不過她並未因此而氣餒，反而在總統瓦希德舞弄空拳期間，致力安插副總統府的實際治國班底。而在她領導下的民主鬥爭黨擴張的勢頭，也讓外界注意到，她的治國實力其實比外表更強，甚至有望超過瓦希德。“瓦梅組合”政權最初被譽為“絕佳搭檔”。然而好景不長，瓦希德四處積怨，執政不久就把過去的所有政治盟友變成了仇敵。他迷信憲法賦予的權力，隨意改組內閣；他執法不嚴，政績不佳，對頹靡的經濟和混亂的政局隻會徒呼奈何；他在執政的21個月期間，頻繁出訪，足跡遍及五大洲，然而對內卻疏於治理。鑒於這種情況，梅加瓦蒂決定拉開與瓦希德的距離。