If you can't get Term::ReadLine::Gnu installed (perhaps you don't have the underlying GNU Readline installed or perhaps you don't have XS support), Term::Readline::Perl5 has the same history mechanism as Term::ReadLine::Gnu and it is pure Perl although it requires Term::ReadKey.
Neither Term::ReadLine by itself nor Term::ReadLine::Perl have history. But again as the others in this thread have indicated, the setting of environment variable PERL_RL and what Perl modules you have installed in addition to Term::ReadLine e.g. Term::ReadLine::Gnu or Term::ReadLine::Perl5 matters here.