Monteleone commence à s'occuper de cinéma durant ses années d'études comme responsable du Centre cinématographique universitaire et du cinéclub CinemaUno de Padoue avec ses amis Roberto Citran et Carlo Mazzacurati. En 1980 il participe à la réalisation de Vagabondi, un film 16mm de Carlo Mazzacurati qui sera primé à Milan.
En 1982 il part à Rome et passe des années difficiles ou il fait un peu de tout: il écrit un press-book pour Gaumont et United Artists, travaille pour la télévision, écrit les dialogues en italien de Nightmare, fait assistant réalisateur pour un film de télévision en Amazonie. En 1986 il réalise son premier scénario : Hotel Colonial, une coproduction italo-américaine avec Robert Duvall, John Savage, Rachel Ward et Massimo Troisi réalisée par Cinzia TH Torrini.
En 1994 il perce comme réalisateur avec La vera vita di Antonio H., présenté au Festival de Venise, une biographie tragicomique d'Alessandro Haber qui apporte un prix Fice à Enzo Monteleone[1].
Ormai è fatta! (1999) est le deuxième film de sa réalisation. Présenté au Festival de Moscou, et récompensé par la Fédération européenne des cinémas d'essai au Festival d'Annecy, dans lequel Stefano Accorsi reçoit un « Calice d'or » (Grolla d'Oro) du meilleur acteur protagoniste, et Arnaldo Catinari le premier prix du Festival international des directeurs de la photographie de Madrid, et qui a été nommé quatre fois au David di Donatello 2000[1].
El Alamein - La linea del fuoco, réalisé en 2002, raconte la résistance désespérée puis la terrible retraite dans le désert d'une compagnie de soldats italiens durant une des plus meurtrières batailles de la Seconde Guerre mondiale sur le Front d'Afrique du Nord. Ce film a remporté trois prix David di Donatello (meilleure photographie, meilleur montage, meilleure musique), deux Globes d'Or (meilleure photographie, meilleur jeune acteur), un Ruban d'argent, un prix Fellini pour la musique, un prix Mastroianni à Pierfrancesco Favino, un prix De Sica à Enzo Monteleone[1].
En 2004 il réalise pour Canale 5 un film en deux parties intitulé Il tunnel della libertà avec Kim Rossi Stuart. Basé sur une histoire véridique il raconte le projet réalisé en 1962 à Berlin-Est par deux étudiants italiens qui ont réussi à faire fuir une trentaine de personnes en creusant un tunnel sous le Mur de Berlin. Le film a remporté La Navicella du Centro Studi Cinematografici de Rome comme meilleure fiction de l'année. Toujours pour Canale 5 il réalise en 2005 la minisérie Il capo dei capi, six épisodes sur la vie criminelle de Totò Riina et du clan des Corleonesi qui obtient un grand succès auprès du public et de la critique: Telegatto de la meilleure fiction de l'année, « Calice d'or » (Grolla d'Oro) de la meilleure réalisation et du meilleur acteur, Prix Kodak-Technicolor au Roma Fiction Festival.
En été 2011 il tourne pour la Rai 1 le film en deux épisodes Walter Chiari - Fino all'ultima risata, la vie aventureuse du célèbre acteur italien Walter Chiari, semée de succès et d'échecs, d'amours fameuses, d'arrestations retentissantes, et interprété par un extraordinaire Alessio Boni.