Naveen Patnaik was elected as the chief minister of Odisha for the first time in 2000 after NDA secured a landslide victory in the 2000 Odisha Legislative Assembly election. The elections were held in February 2000 in two phases. NDA secured 107 seats out of 147 in the twelfth Odisha Legislative Assembly. BJD secured 69 seats while BJP secured 38 seats.
Due to poor handling of 1999 Odisha cyclone and rise in corruption & criminal cases etc. led to rise of unpopularity of Congress, which eventually led to their dismissal performance in 2000 election.
Chief Minister Naveen Patnaik along with 14 Cabinet Ministers, 6 Minister of State with Independent Charges and 4 Minister of State were administered the oath of office and secrecy by Governor M. M. Rajendran at the Raj Bhavan, Bhubaneswar on 5 March 2000. The BJD had the larger share of representation in the ministry with 16 ministers including the Chief Minister while the BJP had 9.
Cabinet reshuffle took place on 6 August 2002 with induction of 8 new ministers.
Assembly was dissolved early almost a year ahead & election were called in line with 2004 Indian general election. NDA lost the general election but won 2004 Orissa Assembly election. Mr. Patnaik resigned on 15 May 2004 paving way for new govt.