Även om prostitution är lagligt i Frankrike, är det inte så att man söker offentligt och hallickar.
Nationalförsamlingen röstade för 16 månader sedan för att införa en â ¬ 1.500 (Â £ 1.090; $1.600) böter på klienter, flytta den kriminella bördan från prostituerade.
Överhusets beslut att skrota böterna kommer nu att gå tillbaka till sammankomsten.
Socialminister Marisol Touraine sade att måndagskvällens omröstning var "absolut otrolig och föraktfull mot kvinnor".
Men Joelle Garriaud-Maylam, en konservativ senator, hävdade att brottet att be om hjälp var en användbar resurs för myndigheterna. "För att hjälpa kvinnorna måste man först identifiera dem."
Den första flytten till att flytta straff från prostituerade till sina klienter följde en svensk lag som gjorde det till ett brott att köpa sex men inte att sälja det. Stödmottagarna hävdade att flytten skulle bidra till att ta itu med nätverken för människohandel.
En svensk regeringsrapport tydde på att 1999 års lag hade lett till en dramatisk minskning av antalet kvinnor som arbetar som prostituerade. Men lagens verkan är inte helt klar eftersom många prostituerade har flyttat från gatorna och vidare till internet.
Frankrike har uppskattningsvis 30 000 sexarbetare och inrikesdepartementet säger att de flesta kommer från Östeuropa, Afrika, Kina och Sydamerika.
Socialister som stödde Frankrikes lagförslag från 2013 om att kriminalisera att betala för sex, snarare än att begära det, hade inledningsvis hoppats att rättegången mot den tidigare Internationella valutafondens chef Dominique Strauss-Kahn skulle kunna påverka den konservativa senaten.
Maud Olivier, en socialdemokratisk parlamentsledamot, sade att rättegången hade lyst ett ljus över sanningen bakom eskorternas värld. "Det finns inget val; våld är någonsin närvarande", berättade hon för tidningen Le Monde.
Rättegången var blåmärken för Strauss-Kahn, som uthärdade en spänd tid inför anklagelser om grov hallick, eftersom flera kvinnor vittnade mot honom innan de lade ner sitt fall.
Han förnekade att kvinnorna var prostituerade. Domen väntas i juni.
Frankrikes senat har förkastat en planerad lag 2013 som straffar människor som betalar för sex, och har valt att upprätthålla brottet att begära.