La iniciativa d'aquests jardins va ser de l'aristòcrata Joan Antoni Desvalls i d'Ardena, VI marquès de Llupià, III marquès del Poal i marquès consort d'Alfarràs, qui va comprar els terrenys el 1791. La finca original comptava amb 54,07 ha d'extensió, de les quals es destinen actualment 9,10 ha a parc públic i la resta a bosc.[1] En aquell temps Horta era un municipi independent, que va ser annexionat a la ciutat de Barcelona el 1904.[2]

Joan Antoni Desvalls (1740-1820) era el típic personatge il·lustrat de l'època, interessat per les ciències i les arts, amb coneixements de matemàtiques, ciències físiques, història, economia i belles arts; dominava el francès i l'italià.[3] Va ser deixeble i col·laborador del matemàtic i filòsof Tomàs Cerdà, i va ser vicepresident de la Reial Acadèmia de Ciències i Arts de Barcelona entre 1799-1808 i 1814-1820. Va escriure diversos treballs sobre física, zoologia i meteorologia, com la Disertación sobre los terremotos de 1783 o El aerómetro o pesalicores de 1791.[4] El 1808 va contribuir a la resistència contra les tropes napoleòniques i, el 1812, va ser triat representant de Barcelona a les Corts de Cadis, on no va assistir per motius de salut.[5]

Les obres es van iniciar el 1794. El mateix Desvalls va intervenir en el disseny del jardí, d'estil neoclàssic, amb la col·laboració de l'arquitecte italià Domenico Bagutti. L'execució de les obres va ser a càrrec del mestre d'obres Jaume Valls i el seu fill Andreu, mentre que de les plantacions se'n va encarregar el jardiner francès Joseph Delvalet.[6]

A mitjans del segle xix els descendents del marquès van ampliar el parc, sota la direcció de l'arquitecte Elies Rogent, pel costat del torrent d'en Pallós, amb un «jardí romàntic» amb parterres, places, grans arbres i una cascada. A més, es va afegir al jardí neoclàssic un canal d'aigua entre la terrassa superior i la intermèdia, construït el 1853. L'ampliació va ser promoguda per Joaquim Desvalls i Sarriera, VIII marquès de Llupià i V d'Alfarràs.[7]

El 1880 es va crear un «jardí domèstic» al costat del palauet Desvalls, d'estil eclèctic. Comptava amb un hivernacle —desaparegut en la restauració de 1971—, una plantació de camèlies i realitzacions d'art topiària.[8] La iniciativa va ser del XI marquès de Llupià i VII marquès d'Alfarràs, Joan Baptista Desvalls i d'Amat, però s'ignora l'artífex d'aquesta ampliació.[7]

Els jardins van ser escenari de recepcions als reis Carles IV (1802), Ferran VII (1828) i Alfons XIII (1908 i 1930).[9] El 18 d'octubre de 1802 van visitar els jardins Carles IV, la seva dona Maria Lluïsa de Parma i els seus fills Ferran (amb la seva dona Maria Antònia de Borbó-Dues Sicílies), Carles, Francesc, Maria Isabel (amb el seu marit Francesc Gener), Maria Lluïsa (amb el seu marit Lluís I d'Etrúria) i Maria Amàlia (amb el seu marit Antoni Pasqual de Borbó). A la base del mur del pavelló anomenat de Carles IV hi ha una làpida de marbre amb una inscripció al·lusiva a la visita del monarca:

El motiu del viatge van ser les noces entre Ferran i Maria Antònia i entre Maria Isabel i Francesc Gener (Maria Antònia i Francesc eren també germans).[11] El baró de Maldà va recollir la visita reial al seu Calaix de sastre:[11]

Ferran VII va visitar la finca el 20 de març de 1828, al costat de la seva dona Maria Josepa Amàlia de Saxònia. El monarca reposava en el Palau Reial de Barcelona d'un atac de gota. En record d'aquesta visita es van col·locar els dos lleons que hi ha en la porta del jardí dels Boixos, que sostenen uns escuts amb la inscripció «A S. R. M. Don Fernando VII En celebridad de su augusta presencia. A S. R. M. Doña Josefa Amalia. En esta quinta día 20 marzo 1828».[12]

Al tombant del segle xix al xx, aquesta finca es va convertir en l'escenari de vetllades socials i culturals amb representacions de teatre a l'aire lliure: el 10 d'octubre de 1898 es va estrenar la tragèdia Ifigènia a Tàuride de Goethe, traduïda per Joan Maragall i dirigida per Adrià Gual; el 1908, en ocasió de la visita d'Alfons XIII, es va representar El somni d'una nit d'estiu, de William Shakespeare, traduïda per Josep Carner i dirigida igualment per Adrià Gual.[13] El rei va acudir-hi acompanyat de la seva dona, Victòria Eugènia de Battenberg, el 23 d'octubre de 1908. En el seu honor es va col·locar el pilar commemoratiu que hi ha al costat de l'entrada del laberint, amb la següent inscripció: «SS. MM. Los reyes Alfonso XIII y doña Victoria Eugenia honraron con su visita estos jardines el día 23 de octubre de 1908».[14]

El 1930, amb motiu d'una nova visita del rei en ocasió del Centenari del Romanticisme, va haver-hi representacions de dansa clàssica a càrrec del cos de ball del Teatre del Liceu, dirigit per Paula Boronat.[15] La representació va tenir lloc el 5 de juny, organitzada per Santiago Marco, president de Foment de les Arts Decoratives. El rei va acudir acompanyat de la seva dona i de nombroses autoritats civils i eclesiàstiques. A més de les danses es van recitar poemes i es va servir un berenar de llet, xocolata, ensaïmades i neules.[16]

El 1968 la família Desvalls va negociar amb l'Ajuntament de Barcelona la venda de la finca. Per a ells el manteniment de la propietat era costós i no podien treure'n rendiment, ja que la finca estava qualificada com a parc urbà en el Pla Comarcal de 1953.[17] Es va establir el valor de la propietat en 70.691.000 pessetes, que van ser abonades a través d'una permuta amb un terreny de valor similar situat a Pedralbes. Aquest terreny, de 9.265 m², es trobava entre l'avinguda del Generalísimo Franco (actualment Diagonal), la plaça de Pius XII, l'avinguda de la Victòria (actualment Pedralbes) i el carrer del Doctor Ferran. L'acta notarial va ser signada per ambdues parts el 17 de gener de 1968.[18]

Després d'una restauració efectuada per Joaquim Casamor, director de Parcs i jardins de Barcelona entre 1968 i 1986, el parc va ser obert al públic el 1971. Entre els treballs efectuats per a la seva rehabilitació poden ressenyar-se: neteja i dragatge de mines, construcció de canalitzacions de reg, instal·lació de la xarxa d'enllumenat, delimitació del parc urbà, col·locació de murs i tanques, instal·lació de serveis públics i mobiliari urbà, reconstrucció d'obres arquitectòniques i rehabilitació del laberint i altres espècies vegetals. També es van restaurar algunes estàtues, a càrrec de l'escultor Josep Miret, mentre que el ceramista Josep Brossa va restaurar les balustrades i els gerros del jardí. La inauguració del nou parc va tenir lloc el 18 de març de 1971, presidida per l'alcalde Josep Maria de Porcioles i amb l'assistència de Lluís Desvalls i Trias, IX marquès d'Alfarràs.[19]

El 1994 va ser sotmès a una nova restauració amb fons de la Unió Europea, a càrrec de Patrizia Falcone. El motiu principal va ser la recuperació de diversos elements tant vegetals com ornamentals que s'havien degradat des dels anys 1970, degut principalment a l'excessiva afluència de visitants. Es va plantar un total de 80.264 plantes de 75 espècies diferents i es va recuperar el circuit hidràulic original. En el jardí romàntic es va crear un circuit tancat per reaprofitament de l'aigua. El cost de la restauració va ser de 80 milions de pessetes. El 25 de setembre de 1994 es va procedir a una reinauguració del parc, presidida per l'alcalde Pasqual Maragall.[20]

El 2006 s'hi va rodar una escena de la pel·lícula El perfum del director Tom Tykwer. En la ficció el laberint pertany al jardí d'un ric hisendat de la ciutat francesa de Grasse, Antoine Richis (interpretat per Alan Rickman), la filla del qual serà l'última víctima de l'assassí Jean-Baptiste Grenouille (Ben Whishaw) i l'element essencial del seu perfum.[21]

Actualment, el parc és un jardí-museu amb un nombre de visitants limitat (màxim 750 persones al mateix temps), per preservar l'àmbit natural i les estructures de l'àrea. L'antic palau acull des del 1993 el Centre de Formació del Laberint, institut municipal per a la formació en jardineria, així com una biblioteca especialitzada igualment en jardineria.[22]

El 2016 el departament de Parcs i jardins va procedir a una reforma de la xarxa hidràulica del parc, després de la detecció d'unes fugides d'aigua en algunes de les seves fonts. En una intervenció que va durar deu mesos, els operaris del parc van procedir al buidatge de l'estany superior, del canal romàntic i de disset fonts; posteriorment van impermeabilitzar aquests espais i els van connectar a una nova xarxa hidràulica, amb alguns elements connectats en circuit tancat per a l'estalvi d'aigua.[23]