Det tidigare namnet kommer av Hammarby vintertull, en av Stockholms tullar där avgift togs ut på varor som fördes in till staden med släde vintertid över frusna sjöar i nuvarande Nacka och Värmdö kommuner. Själva tullhuset, som revs 1907, låg i nuvarande hörnet Malmgårdsvägen-Ljusterögatan. Namnet Vintertullsparken fick parken 1979.[1]
Namnbyte
I september 2013 enades Stockholms stad, Namnberedningen och Anna Lindhs anhöriga om byte av namn för Vintertullsparken till Anna Lindhs park. Anna Lindh bodde länge i närheten av parken. Både Vintertullsparken och Anna Lindhs plats upphör därmed som namn och platsen vid Åsötorget blir namnlös igen.[2]
Skyltar med det nya namnet sattes upp i mars 2014.[3]