Cholodenko is a Ukrainian surname. Notable people with the surname include:
- Alan Cholodenko, American-Australian film theorist
- Lisa Cholodenko (born 1964), American screenwriter and director of film and television
- Marc Cholodenko (born 1950), French writer
- Avraham Cholodenko, Zionist leader and educator