Mate searching is a risky behavior that decreases survival by increasing predation risk and the risk of energy depletion. However, few studies have quantified actual mortality during mate search, making it difficult to predict mate searching and mating strategies. Using a mark and recapture study, we examined mate-searching success in a highly sexually dimorphic species, the golden orb-web spider (Nephila plumipes). We show that despite the high-density aggregations of this species, male survival during mate searching is extremely low (36%) and is phenotype independent. Surprisingly, males that survived mate search were in better condition after recapture than prior to release, most likely due to kleptoparasitism on females' webs. In a complementary release experiment in a field enclosure, we show that males are choosy and adjust their choice of female depending on their own condition and weight. Thus, the high mortality rate of searching males in the field may be a cost of choosiness because released males traveled further than necessary to settle on females. Although males were choosy about female phenotypes, they did not avoid webs with rival males already present. This suggests that the cost of continued searching outweighs the cost of competition but not the cost of mating with certain females. Further examinations of mate-searching risk in other species in reference to their mating system and environmental conditions are necessary to determine the occurrence and effects of high mortality rates during searching.