Utmärkelsen, som är Polens högsta statsorden, tilldelades Zelenskyj under högtidliga former av dåvarande president Andrzej Duda år 2023.
Zelenskyj har nu skickat tillbaka medaljen efter beslutet från president Karol Nawrocki, rapporterar BBC News.
Bråket handlar om Ukrainas beslut att ge ett militärt elitförband namnet "UPA:s hjältar". UPA, Ukrainska upprorsarmén, hyllas i Ukraina som en rörelse för nationell självständighet. I Polen ses den i stället som nazikollaboratörer och förknippas med etnisk rensning och massmord på cirka 100.000 civila polacker i Volynien under åren 1943–1945.
Nawrocki har kallat Ukrainas beslut upprörande och djupt nedslående.
– För den överväldigande majoriteten av det polska samhället är UPA framför allt en formation som bär ansvar för de brutala brott som begicks mot Republiken Polens medborgare under andra världskriget, säger han i en video som publicerats på presidentens officiella webbplats.
Agnieszka Jedrzak, stabschef hos Nawrocki, går på X till hårt angrepp mot Kievs linje. Hon kopplar frågan till Polens stöd till Ukraina under kriget mot Ryssland.
"Man hedrar inte dem som mördade förfäderna till dem som hjälpte en när det gällde liv och död", skriver hon.
Hon fortsätter:
"Vi stöder Ukraina, men vi kommer inte att låta oss förolämpas."
Zelenskyj har svarat att Ukraina vill hålla dörren öppen för samtal med Polen om den gemensamma historien.
I ett uttalande på sociala medier skriver han att Ukraina kommer att "förbli öppet för alla meningsfulla former för samtal med Polen för att försöka undvika motstridiga tolkningar av de svåra och smärtsamma kapitlen i vår gemensamma historia".
Han skriver också att Ukraina är "tacksamt mot det polska folket för deras stöd och samarbete".
Enligt BBC har tre högt uppsatta ukrainska företrädare också sagt att de lämnar tillbaka polska utmärkelser i protest.
Polens premiärminister Donald Tusk manar samtidigt parterna att dämpa konflikten. På sociala medier skriver han att en fejd mellan Zelenskyj och Nawrocki "gläder" Vladimir Putin och uppmanar dem att "lugna känslorna, inte elda på spänningarna".
Fria Tider rapporterade tidigare i juni om att Ukrainas president Volodymyr Zelenskyj även fått kritik från Israel efter att ha gett statliga hedersbetygelser åt Andrij Melnyk. Melnyk ledde en av falangerna inom OUN under den tid då rörelsen samarbetade med Nazityskland.
