We have obtained mosaic images of NGC 3109 in the V and I bands on 74 nights, spanning approximately 1 yr. 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+/-0.03 mag in V and 25.66+/-0.03 mag in I. The distance modulus derived from the reddening-independent V-I Wesenheit index turns out to be significantly shorter (25.54+/-0.03 mag), which indicates that in addition to the foreground extinction of E(B-V)=0.05 mag, there is an intrinsic to NGC 3109 reddening 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 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. Based on observations obtained with the 1.3 m Warsaw telescope at Las Campanas Observatory.