Γεννήθηκε στην Αθήνα στις 21 Δεκεμβρίου του 1918. Το 1939 μπήκε στη Σχολή Καλών Τεχνών. Το 1940 έλαβε μέρος στην Εθνική Αντίσταση, συμμετέχοντας στο Ε.Α.Μ. Εκείνη την εποχή γνώρισε την Γιάννα Περσάκη, εικαστική δημιουργό και μετέπειτα σύντροφο του ποιητή Μίλτου Σαχτούρη, η οποία εργαζόταν στην Εθνική Τράπεζα στην Αθήνα και υπήρξε ενεργό μέλος του Ε.Α.Μ τραπεζοϋπαλλήλων. Την παντρεύτηκε το 1943. Το 1945 μαζί με άλλους νέους διανοούμενους όπως ο Κύρου, ο Καστοριάδης και ο Σβορώνος, ο Κουλεντιανός επιβιβάστηκε στο πλοίο «Ματαρόα» για να ταξιδέψει και να εγκατασταθεί στο Παρίσι, στη Γαλλία. Ήταν η εποχή που η Γαλλία παρέσχε τις περίφημες κρατικές υποτροφίες και ο Κουλεντιανός κατάφερε να σπουδάσει στην Academie de la Grande Chaumiere. Ταυτόχρονα συμμετείχε στο εργαστήρι του Ζάτκιν στην Grande Chaumiere. Τότε ο καλλιτέχνης χειραφετείται και απελευθερώνεται από την ακαδημαϊκή αντίληψη της Σχολής Καλών Τεχνών της Αθήνας. Το 1946, ένα χρόνο μετά τον σύζυγό της, η Γιάννα Περσάκη εγκαταστάθηκε στο Παρίσι, αλλά η σχέση τους τερμάτισε εκεί, μετά από τρία χρόνια γάμου. Αργότερα ο Κώστας Κουλεντιανός παντρεύτηκε με την Joy Gilligan και απέκτησαν μαζί ένα γιο.
Καθοριστική είναι για τον Κουλεντιανό η γνωριμία του με τον Henri Laurens το 1947. Πολλά από τα έργα του είναι επηρεασμένα από τον καλλιτέχνη. Ο Κώστας Κουλεντιανός πραγματοποίησε την πρώτη του ατομική έκθεση στο Παρίσι το 1962, στην Galerie de France και συγχρόνως άρχισε να συνδιαλέγεται με Αρχιτέκτονες για την ένταξη της γλυπτικής στην αρχιτεκτονική, σε δημόσιους και ανοιχτούς χώρους. Παρουσίασε έργα του σε πολλές ατομικές και ομαδικές εκθέσεις στην Αθήνα, το Παρίσι, το Λονδίνο, τη Νέα Υόρκη, τη Λυών, τις Βρυξέλλες. Ασχολήθηκε με την ταπισερί, την χαλκογραφία και την εικονογράφηση. Εικονογράφησε την ποίηση του Σεφέρη (Στέρνα). Την περίοδο 1975 – 1976 δίδαξε στη Σχολή Les Art Deco του Παρισίου και το 1979 – 1980 στη Σχολή Καλών Τεχνών της Μασσαλίας. Από το 1979 μέχρι το 1982 δημιούργησε τη σειρά έργων με τίτλο «Νέα Γενιά», με την οποία αντιπροσώπευσε την Ελλάδα στην Μπιενάλε της Βενετίας το 1980.
Πολλά έργα του, επίτοιχα, ανάγλυφα από ξύλο, μεταξοτυπίες, ανοξείδωτο ατσάλι και επιχρυσωμένο ορείχαλκο, καθώς και ταπισερί, βρίσκονται σήμερα στη Νότια Γαλλία, την Ελλάδα και αλλού. Αρκετά από αυτά κοσμούν δημόσια κτίρια και ανοικτούς χώρους. Δύο γλυπτά του βρίσκονται στον Σταθμό Εθνικής Άμυνας του Μετρό και μπροστά από το ξενοδοχείο Hilton των Αθηνών. Του απονεμήθηκε η διάκριση του «Ιππότη των Τεχνών και των Γραμμάτων» στη Γαλλία. Πέθανε το 1995 στο Πλαν ντ’Οργόν (Plan-d´Orgon), κοντά στη Μασσαλία.
Ο Κώστας Κουλεντιανός μιλάει για τα έργα του:
«Χρησιμοποιώ ως υλικό κυρίως το σίδερο, όλο και πιο σκληρό, πιο βαρύ, πιο δύσκολο να το δουλέψεις. Προσπαθώ ταυτόχρονα να του αφαιρέσω το ακατέργαστο βάρος του και να του δώσω μια άλλη κίνηση… Το βασικό μου πρόβλημα είναι ο χώρος, το φως και ο όγκος. Το πώς το εκάστοτε έργο μου θα μπορέσει να τοποθετηθεί στο χώρο και να δεχτεί το φως, ώστε να αποκτήσει σημασία. Προσπαθώ μέσα από τις φόρμες μου να διανοίξω το χώρο κάνοντας τρύπες για να μπορέσει να περάσει το φως, για να μπει ο χώρος μέσα στο αντικείμενο, το οποίο με τη σειρά του μπαίνει μέσα στο χώρο».
Η Γκαλερί Μέδουσα φιλοξενεί σε μία μικρή αίθουσα μία έκθεση με επιτοίχια και ανάγλυφα έργα του από ξύλο, ανοξείδωτο ατσάλι και επιχρυσωμένο ορείχαλκο και μερικές μεταξοτυπίες.
