Xenakis nasceu em Braila (Roménia), a 29 de Maio de 1922, no seio de uma família de armadores gregos. Viveu nessa região até aos dez anos, familiarizando-se com o rico folclore do vale do Danúbio e com a música bizantina do rito ortodoxo. Em 1932, a sua família regressou à Grécia e foi enviado para um colégio particular, na ilha de Spetsai, onde concluiu os estudos secundários. Estudava engenharia civil no Instituto Politécnico de Atenas quando deflagrou a Segunda Guerra Mundial e a Grécia foi invadida pelas tropas de Mussolini. Juntou-se à resistência comunista em 1941 e, em 1945, sofre um acidente com a deflagração de uma bomba, que lhe deixa para sempre uma cicatriz na cara e o faz perder a visão do olho esquerdo.
Foi capturado e condenado à morte, mas escapou para França em 1947, onde permaneceu como refugiado político até 1965, altura em adquiriu a nacionalidade francesa. Em 1953 casou com Françoise, prolífica escritora e jornalista, de quem teve uma filha, Makhi, que é hoje pintora e escultora.
Até chegar a França, Xenakis tinha sido um músico autodidacta, mas a capital francesa permitiu-lhe o contacto com Honegger, Milhaud e Messiaen, com quem estuda composição. Este último mostra-se especialmente impressionado com a sua originalidade e aconselha-o a
permanecer "ingénuo e livre".
É também nesta época que conhece o célebre arquitecto Le Corbusier, que o contrata como colaborador. Xenakis é envolvido nos estudos de projectos importantes como o Convento de La Tourette, a Assembleia de Chandigarh ou o Estádio de Baghdad, mas o fruto mais marcante desta colaboração é o original Pavilhão Philips da Exposição de Bruxelas de 1958 (baseado em superfícies derivadas de uma mesma linha parabólica), que serviria de palco à apresentação da obra electroacústica de Varèse "Poème Electronique".
Esta revolução arquitectónica encontra um equivalente na revolução musical patente na sua primeira obra publicada, "Metastasis". Estreada no Festival de Donaueschingen, em 1955, provoca um verdadeiro escândalo. Xenakis não vê nenhuma divisão entre as teorias que desenvolve na arquitectura e na música. A problemática do som liga-se permanentemente à sua obsessão pelo espaço.
Com o advento da tecnologia, Xenakis passou a aplicar as suas teorias a programas informáticos. Foi um dos primeiros a recorrer ao computador na composição musical, mais especificamente a um IBM 7090, que usa para conceber "ST48" (1962) e, para estimular a investigação, fundou, em 1966, o Centre d'Études de Mathematique et Automatique Musicales (CEMAMu). Nas décadas subsequentes, viajou por todo o mundo, acompanhando as apresentações das suas obras, proferindo conferências e orientando cursos de composição e estética. Leccionou na City University, em Londres, na Universidade de Indiana e na Sorbonne em Paris (1972-89).