Moustaki se narodil v roce 1934 v egyptské Alexandrii, vyrůstal však na řeckém ostrově Korfu v rodině, kde se mísila řada kultur, kromě francouzské a řecké třeba i turecká nebo arabská. V Paříži žil od padesátých let. Nejdříve se zkoušel živit jako novinář, později dělal barmana.
V Paříži poznal i Edith Piaf, kterou později považoval za svůj vzor. Pro ni a další zpěváky psal texty a stal se také jedním z jejích četných milenců. Pro Piafovou napsal mimo jiné text známé písně Milord. Dále je autorem slavných textů, jako jsou Sarah, Joseph nebo Ma liberté.