Direktivet, som trädde i kraft förra helgen, fördömdes och förlöjligades i stor utsträckning över hela landet.
När det gäller kvinnor i östra Libyen förbjöd det dem som var under 60 år att resa utomlands utan en manlig förmyndare.
Myndigheterna hade sagt att förbudet var av säkerhetsskäl, inte av religiösa skäl.
En militär tjänsteman hävdade att det berodde på att vissa kvinnor som reste utomlands hade kontakt med utländska underrättelser.
Myndigheterna lade inte fram några bevis för detta påstående.
Frysningen av reseförbudet tillkännagavs av chefen för det civila samhällets kommission i östra Libyen, Abir Mneina, som hade fört samtal med den militära stabschefen i Libyens östra region, Abdelrazzak al-Naduri, på tisdagen.
Hon berättade för BBC att tjänstemän hade ombetts att upphäva förbudet men gick bara med på att frysa det tillfälligt och genomföra en översyn.
"Han [Herr al-Naduri] sade... det finns säkerhetskonsekvenser som måste beaktas. Vi sade bra, om det finns specifika säkerhetsfrågor då vi förstår och stöder att eftersom vi är i ett tillstånd av krig och detta är en viktig fråga för oss alla, "sade Mneina
"Så det är därför vi slutligen kom överens om att direktivet kommer att ses över för att se till att det inte förekommer några kränkningar mot rättigheter och friheter â € € vårt främsta mål är att få ordern inställd helt.
"Jag tror att vi är på väg mot att det blir inställt. Vi sa att om det inte ställs in så förbereder vi redan ett juridiskt uttalande som kommer att föras till domstol."
En källa på kontoret för östra Libyens stabschef, som talade på villkor av anonymitet, bekräftade för BBC att ordern hade frysts.
Han sade att förbudet håller på att ses över eftersom "det kan ha generaliserat frågan för mycket".
Libyen har varit i kaos sedan Nato-stödda styrkor störtade överste Muammar Khadaffi i oktober 2011.
Östra Libyen styrs av en administration baserad i al-Beyda som inte erkänns av det internationella samfundet. Det är under kontroll av befälhavare Khalifa Hafter som leder kampen mot islamistiska miliser.
Libyens internationellt erkända regering är baserad i huvudstaden Tripoli.
Resrestriktionerna belyste den växande politiska klyftan i Libyen, där båda sidor verkställde sina egna regler på det område som de kontrollerar.
Myndigheterna i östra Libyen har beordrat en tillfällig frysning av ett kontroversiellt reseförbud för libyska kvinnor under 60 års ålder.