We have obtained mosaic images of NGC 3109 in the V and I bands on 74 nights , spanning approximately one year . From these data , we have conducted an extensive search for Cepheid variables over the entire field of the galaxy , resulting in the discovery of 113 variables with periods ranging from 3.4 to 31.4 days . In this sample , 76 Cepheids , including many long-period variables , were not known before . For the previously known 45 Cepheids in this galaxy , our data proved that reported periods were wrong for 14 objects ; for nearly all other previously known Cepheid variables we were able to significantly improve on the periods . We construct period-luminosity relations from our data and obtain reddening-corrected distance moduli of 25.72 \pm 0.05 mag in V , and 25.66 \pm 0.04 mag in I . The distance modulus derived form the reddening-independent V-I Wesenheit index turns out to be significantly shorter ( 25.54 \pm 0.05 mag ) , which indicates that in addition to the foreground extinction of E ( B-V ) = 0.05 mag , there is an intrinsic to NGC 3109 redening of about 0.05 mag . Our distance obtained based on the reddening-free Wesenheit magnitudes is consistent with earlier distance determinations of NGC 3109 from Cepheids , and the tip of the red giant branch . We will improve on our distance and extinction determination combining our optical data with the follow-up near-infrared observations of a subsample of NGC 3109 Cepheids .