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 behavior of these pulsators at very low metallicity regimes is almost unexplored. In order to derive constraints on the application of the PL relation at low metal abundances, we investigate the properties of the few ultra-low metallicity (Z 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 PL 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 toward the lowest Zs.