Områderne syd for Hammelstrupvej kaldtes tidligere Valby Fælled og blev fra 1913 og indtil slutningen af 1930’erne brugt som lossepladser.
Med skrald fra Københavnske husstande blev en del af vandet i Kalveboderne efterhånden fyldt op.
Da brugen af lossepladsen stoppede, begyndte man anlægget af en park, der i første omgang blev på 60 hektar. Anlægsarbejdet blev især udført som beskæftigelsesarbejde i en tid med stor arbejdsløshed.
Parken åbnede for publikum i 1939.
Under Besættelsestiden var der mangel på brændsel, og folk fandt ud af at pille små stumper koks op i parken, som stammede fra lossepladstiden. Derfor måtte parken genetableres i 1940’erne.
Foruden de vidtstrakte græsplæner, blev der plads til fodbold- og skøjtebaner. Der blev desuden anlagt kolonihaver.
Inde i parken anlagdes i 1965 den cirkelrunde Rosenhave med 12.000 roser.
I 1967 fik Valbyparken en trafiklegeplads.
I 1996 blev der etableret 17 runde haver med hvert sit tema. Haverne var en del af markeringen af København for europæisk kulturby.
Samtidig anlagde man fire kunstige søer under navnet Den Grønne Frøpark, hvor der blev levesteder for frøer, tudser m.m. For at gøre opmærksom på arbejdet for at bevare den grønbrogede tudse, opkaldt man i 1999 en nærliggende vej for Tudsemindevej.
I dag er Valbyparken Københavns næststørste park. Kun Fælledparken er større.
Ved indgangen til parken blev i 1959 placeret en stor sten, der blev fundet under udgravningen til Fiskerihavnen ved Bådehavnsgade. Stenen er af gnejs, og stammer fra Mellemsverige, men blev under istiden ført hertil.
Omkring caféen midt i parken blev i 1970 opstillet en stenskulptur med en havtaske som motiv. Kunstneren er Henry Heerup (1907-1993) og anledningen var billedhuggeren Bertel Thorvaldsens 200-års dag.