Новому уряду довелося вирішувати ті ж проблеми, які привели до падіння режиму Сухарто. Під тиском опозиції уряд розпочав кардинальні реформи у галузі економіки і управлінні. Були скасовані ряд привілеїв колишньому президентові і його родині, ослаблений контроль над засобами масової інформації й розширені повноваження провінційних органів влади. У червні 1998 уряд президента Хабібі підтвердив намір провести президентські й парламентські вибори, і до липня були зареєстровані більше 40 нових політичних партій. Парламентські вибори відбулися 7 червня 1999. Виборцям було запропоновано вибрати 462 законодавця із числа 10,5 тис. кандидатів від 48 політичних партій. На перше місце вперше за увесь час свого існування вийшла опозиційна Демократична партія Індонезії, що одержала 153 місця в парламенті і 33,7% голосів. Голкар завоював 120 місць (20,9% голосів), Партія єдності й розвитку - 58 місць (10,7%), Партія національного пробудження - 51 місце (17,1%) і Партія національного мандата - 35 місць (7,3%). 44 мандата, що залишилися розділили 14 партій.
У жовтні 1999 відбулися президентські вибори. Як основні кандидати були висунуті Абдуррахман Вахід (лідер Партії національного пробудження) і Мегаваті Сухартопутрі. Переміг Абдуррахман Вахід, що набрав 373 голоси; Мегаваті одержала 313 голосів і стала віце-президентом. Нова адміністрація зіткнулася з безліччю проблем, включаючи необхідність реформувати систему керування, позбутися від неефективності та корупції, що дісталася в спадщину від адміністрації Сухарто, і вирішити економічні проблеми, що залишилися, в країні.
Новий уряд спробував вирішити застарілу проблему Східного Тимора. У серпні 1998 Індонезія й Португалія прийшли до угоди почати переговори про майбутній автономний статус цієї провінції. На цьому тлі по всій країні почалися релігійні виступи та хвилювання; у Східному Тиморі почали діяти за підтримки армії напіввійськові формування. На початку 1999 посилився конфлікт в Ачехе; усе голосніше лунали вимоги проведення референдуму по незалежності, подібного до голосування в Східному Тиморі. У вересні 1999 для відновлення порядку в Східному Тиморі були розгорнуті війська ООН по підтримці миру, очолювані австралійцями. 20 жовтня 1999 законодавчий орган Індонезії ратифікував результати серпневого референдуму, поклавши початок формальної передачі Східного Тимора в керування ООН. 26 жовтня 1999 ООН офіційно прийняла управління Східним Тимором (з мандатом до 31 січня 2001).
У червні 2000 було підписане перемир'я між урядом і лідерами сепаратистського Руху Вільний Ачех. Перемир'я, більш ніж за два десятиліття насильства, розглядався як перший крок до досягнення миру й остаточного припинення боротьби та порушень прав людини. В іншому місці, у провінції Моллуку, Моллукські острови, спалахнуло насильство між християнськими й мусульманськими громадами. Основною причиною зростаючої напруженості вважається ріст мусульманської міграції, розглянутої християнами як погроза їхнім економічним позиціям. На початку 2000 року спалахами релігійного насильства були відзначені в Ломбоке, Сумбаве і на Сулавесі. Продовжили наростати безладдя на Молукських островах, де в червні 2000 президент Вахід оголосив надзвичайний стан.
Однак наприкінці 2000 президент Вахід зіштовхнувся з обвинуваченнями в корупції й незаконному присвоєнні пожертвувань (у розмірі 6,1 млн. дол.). Хоча слідство не довело, що Вахід прямо або побічно отримував хабарі, скандал привів до закликів щодо відставки президента. Крім обвинувачень у корупції, його звинуватили, що він не зміг зупинити етнічне насильство. 1 лютого 2001 парламент переважною більшістю (393 голосів проти 4) виніс президентові вотум недовіри. Це питання повторно обговорювалося в парламенті у квітні того ж року.
Вахід відхилив обвинувачення як необґрунтовані та проігнорував вимоги про свою відставку. Після цього законодавчий орган проголосував за те, щоб у серпні почати слухання по процедурі імпічменту президента. Однак президент пішов на випередження і у липні 2001 видав декрет про ведення в країні надзвичайного стану та призупинення діяльності законодавчого органу. На вулиці вийшли десятки тисяч прихильників президента, готові його захищати. 23 липня 2001 Народний консультативний конгрес, скликаний на надзвичайне засідання, проголосував за відсторонення Абдурахмана Вахіда від влади за обвинуваченням у некомпетентності і корупції. Він був замінений віце-президентом Мегаваті Сухартопутрі, дочкою першого президента Сухарто. Віце-президентом Індонезії став Хамза Хаз, глава Партії єдності й розвитку. Відвідавши Ачех і почавши азіатський тур по дев'яти країнах, вона пообіцяла покласти кінець корупції в країні.
Тим часом основними проблемами, якими довелося займатися кабінету Мегаваті, стали питання безпеки й боротьби з тероризмом. У грудні 2000 на Яві і Суматрі прогриміли вибухи в католицьких церквах; у результаті загинуло 15 чоловік. Ісламські екстремісти готували замах на президента. Після терористичних нападів на Нью-Йорк і Вашингтона в 2001, Мегаваті була першою серед лідерів мусульманських країн, що відвідали США, щоб виразити свою моральну підтримку.
Протягом усього наступного року в Індонезії не припинялися антиамериканські й антизахідні виступи, спровоковані операцією США в Афганістані й погрозою вторгнення в Ірак. Однак найбільш радикальні угруповання організовували теракти. У результаті вибухів, що відбулися 12 жовтня 2002 у нічних клубах на Балі, були вбиті 202 чоловік, головним чином, туристи, і 326 чоловік поранені. Ще одна бомба вибухнула перед консульством США в Санурі, Балі, не заподіявши ніякої шкоди. Індонезійський уряд у відповідь на вибухи на Балі, надав поліцейським широкі повноваження, щоб переслідувати терористів. За участь у терористичних актах в 2003 до страти були засуджені Амрозі ібн Нурхасім і Імам Самудра, члени «Джемаа ісламія», ісламістської терористичної групи, пов'язаної з « Аль-Каідою».
У серпні 2003 вибух бомби біля готелю «Меріот» у Джакарті призвів до 16 жертв; 152 чоловік були поранені. Офіційна влада поклала відповідальність за злочин на угруповання «Джемаа ісламія», Незабаром після цього, 16 листопада 2003, був прийнятий закон про боротьбу з тероризмом. Однак уже в липні 2004 Конституційний суд оголосив антитерористичний закон, як той, що суперечить конституції і не має юридичної дії.
Продовжуючи боротьбу з тероризмом, уряд в той же час намагався мирним шляхом врегулювати етнічні конфлікти. У грудні 2002 була підписана угода із сепаратистами з Руху за вільний Ачех. В обмін на роззброювання населення провінції була обіцяна автономія й проведення прямих виборів. Однак уже в травні 2003 президент Мегаваті Сухартопутрі оголосила в Ачеху воєнний стан; армією було почата військова операція проти повстанців, що привело до величезних жертв серед мирного населення.
У серпні 2002 індонезійський парламент, Рада народних представників, схвалив виправлення, що передбачає всенародні вибори президента й віце-президента Республіки, починаючи з 2004.
5 квітня 2004 відбулися вибори в законодавчі органи влади Індонезії, що проходили за новою схемою. Виборцям пропонували визначити склад нового органу регіонального представництва, а також обрати всіх депутатів нижньої палати парламенту. Підрахунок більше 113 млн. голосів зайняв рівно місяць. По їхніх результатах Партія Голкар, на чолі з Акбаром Танджунгом, одержала 21,6% голосів і 128 з 550 місць, Демократична партія Індонезії Мегаваті Сухартопутрі зібрала 18,5% голосів і 109 місць. Серед інших партій, що одержали істотну підтримку, були Партія єдності й розвитку - 58 місць, Демократична партія - 57 місць, Партія національного пробудження - 52 місця, Партія національного мандата - 52 місця й ісламістська Партія процвітання й справедливості - 45 місць. Усього у виборах брали участь більше 7,7 тис. кандидатів від 24 політичних партій.

П'ять політичних партій, що найбільше успішно виступили на парламентських виборах, висунули своїх кандидатів для участі в перших прямих президентських виборах, що відбулися у два тури - 5 липня й 20 вересня 2004. Це були перші прямі президентські вибори в історії Індонезії. Кандидат від Демократичної партії, генерал у відставці і колишній міністр безпеки Сусіло Бамбанг Юдойоно, посів перше місце, але не зумів набрати більшість голосів. Тому боротьба в другому турі розгорнулася між Юдойоно й Мегаваті Сухартопутрі. У підтримку Мегаваті виступив блок партій на чолі із ДПІ, Голкар і Нахдлатул Улама, що розраховував у випадку її перемоги на формування коаліційного уряду. Однак, президентом Республіки Індонезії став Сусило Бамбанг Юдойоно, що завоював у другому турі президентських виборів понад 60,9% голосів з 110 млн. виборців, що проголосували. Інаугурація першого всенародно вибраного президента відбулася 20 жовтня 2004. Новий президент пообіцяв ужити негайних заходів, щоб стимулювати мляву економіку Індонезії, покінчити із сепаратистськими заколотами, забезпечити безпека країни й почати реальну боротьбу з корупцією.