In response to the widespread use of control strategies such as Insecticide Treated Nets (ITN), Anopheles mosquitoes have evolved various resistance mechanisms. Kdr is a mutation that provides physiological resistance to the pyrethroid insecticides family (PYR). In the present study, we investigated the effect of the Kdr mutation on the ability of female An. gambiae to locate and penetrate a 1cm-diameter hole in a piece of netting, either treated with insecticide or untreated, to reach a bait in a wind tunnel. Kdr homozygous, PYR-resistant mosquitoes were the least efficient at penetrating an untreated damaged net, with about 51% [39-63] success rate compared to 80% [70-90] and 78% [65-91] for homozygous susceptible and heterozygous respectively. This reduced efficiency, likely due to reduced host-seeking activity, as revealed by mosquito video-tracking, is evidence of a recessive behavioral cost of the mutation. Kdr heterozygous mosquitoes were the most efficient at penetrating nets treated with PYR insecticide, thus providing evidence for overdominance, the rarely-described case of heterozygote advantage conveyed by a single locus. The study also highlights the remarkable capacity of female mosquitoes, whether PYR-resistant or not, to locate holes in bed-nets.