Classical Cepheids are primary distance indicators playing a fundamental role in the calibration of the extragalactic distance scale . The possible dependence of their characteristic Period-Luminosity ( PL ) relation on chemical composition is still debated in the literature , and the behaviour of these pulsators at very low metallicity regimes is almost unexplored . In order to derive constraints on the application of the Period-Luminosity relation at low metal abundances , we investigate the properties of the few ultra-low metallicity ( Z \approx 0.0004 ) Cepheids recently discovered in the Blue Compact Dwarf galaxy IZw18 . To this purpose we have computed an updated and extended set of nonlinear convective models for Z = 0.0004 and Y = 0.24 , spanning a wide range of stellar masses , and taking into account the evolutionary constraints for selected luminosity levels . As a result we are able to predict the topology of the instability strip , the variations of all the relevant quantities along the pulsation cycle , including the morphology of the light curves , the theoretical Period-Luminosity-Color , Period-Wesenheit and Period-Luminosity relations at such a low metallicity . For each of these relations we provide the appropriate coefficients for fundamental mode pulsators with Z=0.0004 . By comparing these results with the properties of more metal rich Cepheids we find that the synthetic PL relations for Z = 0.0004 are steeper than at higher Z , but similar to the Z = 0.004 ones , thus suggesting a leveling off of the metallicity effect towards the lowest Zs .