Parlato nacque a Tripoli, all'epoca capoluogo della provincia omonima (nell'allora Libia italiana), il 7 febbraio del 1931 da genitori italiani, Giuseppe Parlato e Angela Sajeva, originari rispettivamente di Comitini e di Favara (ambedue comuni dell'agrigentino), stabilitisi nella città libica sul finire degli anni venti.
Trascorre un'infanzia tutto sommato tranquilla, almeno fino allo scoppio della seconda guerra mondiale, a causa della quale si ritrova costretto a spostarsi con la famiglia nella campagna di Sorman, dove il nonno materno possiede una piccola concessione agricola. Non potendo studiare, divora la modesta biblioteca familiare: è il germe di una cultura onnivora e curiosa, che lo accompagnerà per tutta la vita; con il nonno impara inoltre a conoscere la vita di campagna, molto diversa da quella piccolo-borghese vissuta nella placida società coloniale tripolitana.
A conflitto concluso, la Libia passa sotto l'amministrazione britannica ed è proprio in questi anni che forma la propria coscienza politica, conoscendo Clara Valenziano - che in seguito sposerà -, comunista militante, e figurando perciò tra i fondatori del Partito Comunista Libico, fatto che ne provocherà l'espulsione dal paese nel 1951. Riparato dunque in Italia, a Roma, dove si iscrive alla facoltà di Giurisprudenza, conosce Luciana Castellina e s'iscrive al Partito Comunista …
