Rising progesterone (P4) levels in humans due to its overconsumption through hormonal therapy, food products, or drinking water can lead to many negative health effects. Thus, the simple and accurate assessment of P4 in both environmental and clinical samples is highly important to protect public health. In this work, we present the selection, identification, and characterization of ssDNA aptamers with high binding affinity to P4. The aptamers were selected in vitro from a single-stranded DNA library of 1.8 × 10(15) oligonucleotides showing dissociation constants (KD) in the low nanomolar range. The dissociation constant of the best aptamer, designated as P4G13, was estimated to be 17 nM by electrochemical impedance spectroscopy (EIS) as well as fluorometric assay. Moreover, the aptamer P4G13 did not show cross-reactivity to analogues similar to progesterone such as 17β-estradiol (E2) and norethisterone (NET). An impedimetric aptasensor for progesterone was then fabricated based on the conformational change of P4G13 aptamer, immobilized on the gold electrode by self-assembly, upon binding to P4, which results in an increase in electron transfer resistance. Aptamer-complementary DNA (cDNA) oligonucleotides were tested to maximize the signal gain of the aptasensor after binding with progesterone. Significant signal enhancement was observed when the aptamer hybridized with a short complementary sequence at specific site was used instead of pure aptamer. This signal gain is likely due to the more significant conformational change of the aptamer-cDNA than the pure aptamer upon binding with P4, as confirmed by circular dichroism (CD) spectroscopy. The developed aptasensor exhibited a linear range for concentrations of P4 from 10 to 60 ng/mL with a detection limit of 0.90 ng/mL. Moreover, the aptasensor was applied in spiked tap water samples and showed good recovery percentages. The new selected progesterone aptamers can be exploited in further biosensing applications for environmental, clinical, and medical diagnostic purposes.