Tras licenciarse con honores en Derecho por la Universidad de Palermo el 27 de noviembre de 1969, Natoli ingresó en la magistratura italiana en 1978, se convirtió en juez instructor en el tribunal de Trapani y, posteriormente, en 1983, en el de Palermo a petición de Rocco Chinnici, pocos días antes de su asesinato.

Entró en el «grupo antimafia» de la oficina de instrucción, dirigido por Antonino Caponnetto, junto con, entre otros, Giovanni Falcone y Paolo Borsellino.

El juez Natoli se ocupó de la instrucción del Maxiproceso de Palermo, de las investigaciones sobre Totò Riina y del asesinato de Pio La Torre, así como de la investigación «Pizza connection»,^[2]​ que se llevó a cabo en Nueva York en colaboración con el FBI y en la que fueron acusados Gaetano Badalamenti y otros mafiosos siciliano-estadounidenses.

En 1991 entró en la fiscalía de Palermo y fue miembro de la Dirección Distrital Antimafia (DDA).^[2]​ Allí, Natoli es encargado de seguir, entre muchos otros, el proceso del eurodiputado Salvo Lima y es el fiscal del proceso del senador Giulio Andreotti, que investigaba las relaciones entre la mafia y la política. Permaneció en estas funciones hasta 1998, cuando fue elegido miembro del Consejo Superior de la Magistratura (CSM), puesto que desempeña hasta 2002. Posteriormente, ocupó el cargo de vicepresidente de la Asociación Nacional de Magistrados.^[3]​

En 2005 fue nombrado presidente del tribunal de apelación de Palermo y, en junio de 2011, presidente del tribunal de Marsala.^[4]​ Natoli se convierte en presidente del Tribunal de Apelación de Palermo en abril de 2015.

En junio de 2016 el ministro Andrea Orlando lo nombró jefe del Departamento de Organización Judicial del Ministerio de Justicia.^[5]​ Se jubiló el 31 de diciembre de 2017.

El 30 de mayo de 2018, el presidente de la Región Siciliana, Nello Musumeci, lo nombró comisario extraordinario de la Cámara de Comercio de Caltanissetta,^[6]​ tras la detención de su presidente, Antonello Montante, cargo que desempeña hasta el 31 de agosto de 2018.

En julio de 2024, la fiscalía de Caltanissetta comenzó una investigación por favorecimiento agravado a la mafia. Según la acusación, «para ayudar a empresarios mafiosos, Natoli habría intentado encubrir una línea de la investigación conocida como “mafia-contratos públicos”».^[7]​^[8]​ La investigación judicial, que avanzaba lentamente, dio un vuelco un año más tarde a raíz del hallazgo realizado el 3 de julio de 2025 de cuatro sobres sellados por la Guardia de Finanzas, con documentos que se daban por desaparecidos y que se encontraron, treinta años más tarde, en el interior de un archivo olvidado en el sótano de la Fiscalía de Palermo.^[9]​ Los sobres, con sello de 1992, contienen las transcripciones de la escucha de conversaciones telefónicas realizadas en los años 90 sobre la infiltración de la Cosa Nostra en el sector empresarial, en particularde los negocios del Grupo Ferruzzi.^[9]​ Natoli, quien desde un comienzo se había acogido a su derecho de no declarar, decidió esta vez responder las preguntas en un extenso interrogatorio que tuvo lugar el 4 de julio de 2025 y que se prolongó por cerca de 12 horas. ^[10]​

• "Cosa nostra ieri, oggi, domani: la mafia siciliana nelle parole di chi la combatte", (con Gianni di Cagno) Ed. Dedalo, 2004, ISBN 8822062701