Paolo Gioli nasce a Sarzano di Rovigo il 12 ottobre 1942, settimo di undici figli di Celio,  geometra, e di Leonina Gasparetto. Frequenta le scuole elementari a Sarzano.  Verso i diciotto anni conosce lo scultore Virgilio Milani e inizia a frequentare il suo studio di Rovigo. E' per lui un primo maestro. Nel 1960 inizia a lavorare come decoratore in un laboratorio di ceramica di Rovigo. Qui conosce Carla Schiesari, che sposerà nel 1969. Dal 1960 al 1963 frequenta la Scuola Libera del Nudo 
Paolo Gioli, Venezia,1963
presso l'Accademia di Belle Arti di Venezia. Conosce Luciano Gaspari e Giuseppe Santomaso, che lo incoraggiano a disegnare e a dipingere, e successivamente Emilio Vedova, mentre l'assidua   frequentazione dei musei e delle gallerie veneziane lo avvicina all'arte italiana del Medioevo e del Rinascimento e le frequenti visite all'Archivio storico della Biennale e alla collezione Guggenheim gli fanno conoscere le avanguardie. Nel 1964 incontra la Pop Art americana, esposta alla Biennale. Nella sua permanenza a Venezia, fino al 1967, conosce il gallerista Cesare Misserotti e, fra gli altri, il critico  Berto Morucchio. Partecipa alle mostre collettive dell'Opera Bevilacqua La Masa, presidente Diego Valeri, nel 1963-'64 (vincitore del primo premio per il disegno, "Nudo", 1963), 1964-'65, 1965-'66 (vincitore del primo premio per la pittura, "Figura, figura, figura, figura", 1965). Nel 1964, '65, '66, '67 espone in mostre personali alla galleria l'Elefante, presso la quale stampa la sua prima cartella litografica, "Oggetti probabili", 1967. Alla fine del 1967 insieme al pittore Piergiorgio Brusegan parte per New York, dove vive per circa un anno. Qui conosce Ruth Friedlich (a lui segnalata dall'allora conservatore di Ca' Pesaro Guido Perocco), la quale gli è d'aiuto e gli fa ottenere una borsa di studio della John Cabot University di Boston. A New York stringe  amicizia con Paolo Vampa, che diviene sostenitore

  Paolo Gioli , Venezia 23 agosto 1966

e produttore del suo lavoro. Gioli vive prima nel quartiere portoricano e poi a Union Square, accanto alla Factory di Andy Warhol. Fa diretta conoscenza dell'Espressionismo Astratto, della Pop Art, del New American Cinema e visita ripetutamente i musei e le gallerie d'arte newyorchesi, e il Museo di Storia Naturale. Lavora ad alcuni grandi disegni (uno di essi è oggi conservato presso la Rockfeller Foundation), ma l'esperienza americana segna soprattutto la nascita di un forte interesse per il cinema e, insieme, di un primo interesse per la fotografia. Nell'autunno del 1968 è di nuovo in Italia e per un anno torna a vivere a Venezia. Nel 1969 inizia a lavorare con il cinema e poi con la fotografia, utilizzando camere con foro stenopeico. Nel 1969 si trasferisce a Roma, dove vive fino al 1975. E' il periodo della Pop Art romana, che vede attivi Schifano, Angeli, Festa. Gioli affianca alla pittura e al disegno la serigrafia e la litografia (realizza una nutrita serie di tele serigrafiche, due cartelle litografiche, "Ispezione e tracciamento sul rettangolo" e "Immagini disturbate da un intenso parassita", 1975 e un libro litografico, "Dadathustra", 1976) e approfondisce sempre di più i suoi interessi verso il cinema e la fotografia, con decisa scelta di stampo sperimentale. Attraverso il filmmaker Alfredo Leonardi entra in rapporto con la Cooperativa Cinema Indipendente, intorno alla quale operano, oltre a Leonardi, pittori come Gianfranco Baruchello e letterati come Massimo Bacigalupo. Presenta al FilmStudio, fondato da Amerigo Sbardella e a cui collaborano Adriano Aprà e Enzo Ungari, i suoi primi film, interamente girati, sviluppati e stampati da lui.