Paul Fenech first achieved prominence by winning third place in Sydney's annual Tropfest short film festival in 1995 for a biographical short entitled Pizza Man based on his experiences as a pizza delivery driver. He won the Tropfest award for best film in 1998 for Intolerance, although he had submitted the film under the pseudonym Laura Feinstein in order to appeal to the sensitivities of the judges, particularly Tropfest founder John Polson, who hoped that a female director would win the award.
He made a documentary called More Than Legends, a documentary that highlighted Aboriginal culture through the eyes of three elders.
Fenech also created the sitcom series Swift and Shift Couriers.