De 1852 jusqu'en 1997, la Compagnie centrale des chemins de fer de l'Illinois, possédait un droit de passage pour ses voies ferrées qui séparaient alors le centre ville de Chicago des rives du lac Michigan. Pendant une brève période en 1871, suite au Grand incendie, l'équipe des Chicago White Stockings jouèrent des matchs sur ce terrain que l'on nommait alors l'Union Base-Ball Grounds. Ce n'est qu'au début du XX siècle que l'architecte Daniel Burnham projeta d'installer Grant Park en ce lieu dans son Plan de restructuration de Chicago de 1909.
En 1997, lorsque la ville repris le contrôle de cette zone, elle décida d'y installer une aire de stationnement. Cependant, la ville réalisa que l'installation d'un parc publique était plus susceptible d'attirer quelques financements privés qu'un parking et elle entreprit alors de créer le Millennium Park. Le parc était alors provisoirement baptisé Lakefront Millennium Park. Le maire de la ville, Richard M. Daley souhaitait créer un nouvel espace dans Grant Park et transformer les abords du lac Michigan occupé par des parcs de stationnement et le site de la Compagnie centrale des chemins de fer de l'Illinois, demeuré inchangé depuis 1902.
Le parc était originellement conçu comme un espace vert de 65 000 m recouvrant un parking sous-terrain qui devait être construit au dessus de la voie ferrée du Metra, la ligne ferroviaire traversant le Grant Park. Au début, le parc a été conçu par l'agence d'architecte Skidmore, Owings and Merrill, mais peu à peu d'autres architectes et artistes ont participé au projet comme Frank Gehry ou Thomas Beeby. En février 1999, la ville a annoncé qu'elle négociait avec Frank Gehry la création d'un proscenium et d'un espace d'orchestre pour un kiosque à musique ainsi qu'un pont piéton enjambant Columbus Drive.
La construction initiale du parc était sous la responsabilité du département des transports dans la mesure où le projet devait enjamber les voies ferrées. Cependant, pendant que le projet se développait et augmentait, sa grande variété d'équipements et d'installations l'a placé sous la juridiction de la commissions des édifices publics.
En avril 1999, la ville annonçait que la Famille Pritzker avait donné 15 millions de dollars pour financer le pavillon Jay Pritzker conçu par Frank Gehry et que neuf autre donateurs avaient apporté 10 millions de dollars supplémentaires. Au mois de juillet 1999, la construction du parking souterrain débutait.
En janvier 2000, la municipalité présenta un nouveau projet pour le parc incluant de nouveaux équipements tels que la Cloud Gate, la Crown Fountain, le McDonalds Cycle Center et la passerelle BP. Au mois de juin, la même année, la ville décide de se séparer des sociétés Schwendener Inc. et Harston Construction Co., les deux entreprises générales en charge du projet avec lesquelles elle n'était pas parvenue à conclure un accord prenant en compte l'augmentation des coûts de construction liés aux modifications du projet.
Malgré l'allongement des délais et l'explosion du budget consacré à la construction et l'aménagement du parc, celui-ci a été achevé avec 4 années de retard et son inauguration, le 16 juillet 2004, a été célébré par un gala financé par la société financière JPMorgan Chase.
