Milena Vukotic è nata a Roma da padre jugoslavo commediografo e da madre italiana, pianista e compositrice. Ha seguito gli studi artistici a Londra, Vienna e, in seguito, a Parigi, dove ha studiato pianoforte, danza e recitazione e ha vinto il primo premio per la danza al Conservatoire National de Musique. Dopo una breve esperienza nel corpo di ballo dell’Opéra, ha fatto parte per alcuni anni della compagnia internazionale Grand Ballet du Marquis de Cuevas e della compagnia di Roland Petit, con le quali ha girato tutto il mondo. Negli anni Sessanta, ha sviluppato la sua carriera teatrale entrando nella compagnia Morelli-Stoppa e lavorando poi con registi come Giorgio Strehler, Franco Zeffirelli, Franco Enriquez, Paolo Poli, Beno Besson, Piero Maccarinelli, Mario Missiroli.
Nel 2002 le è stato assegnato l’importante premio Eleonora Duse in riconoscimento della sua prestigiosa carriera teatrale. Nelle stagioni teatrali più recenti ha interpretato il dramma Lasciami andare madre di Helga Schneider, per la regia di Lina Wertmüller, i monologhi Il piccolo portinaio di Marco Amato, regia di Walter Manfré, e Alice x Alice = Alice di Valeria Moretti, per la regia di Marco Mattolini, e L’amico magico, omaggio a Federico Fellini e Nino Rota, per la regia di Gianfranco Angelucci.
È stata molto attiva anche in televisione, a partire da Gian Burrasca (1964) di Lina Wertmüller, prendendo parte a sceneggiati diretti, tra gli altri, da Guido Stagnaro, Raffaele Maiello, Renato Castellani, Sandro Sequi, Vittorio Cottafavi, Massimo Scaglione, fino alla recente e popolare serie Un medico in famiglia.
Quanto all’attività cinematografica, particolarmente intensa con circa cento titoli all’attivo, è stata chiamata a recitare in film di Alessandro Blasetti, Federico Fellini, Alberto Lattuada, Lina Wertmüller, Mauro Bolognini, Ettore Scola, Mario Monicelli, Carlo Lizzani, Dino Risi, Bernardo Bertolucci, Andrej Tarkovskij, Jean-Jacques Beineix, Nagisa Oshima – nonché di molti altri registi – in ruoli sia drammatici che di genere leggero e comico. È stata interprete degli ultimi tre film del grande Luis Buñuel ed è particolarmente popolare per la serie dei film di Fantozzi - tra il 1980 e il 2000 - in cui interpreta il ruolo della moglie Pina. Tra gli impegni più recenti, A Good Woman, di Mike Barker, e Saturno contro, di Ferzan Ozpetek. Nel 2007 le è stato attribuito il premio Ciak d’oro alla carriera.