Γεννήθηκε το 1760 στον οικισμό Άγριλο, στην σημερινή Πολιανή του νομού Μεσσηνίας. Λόγω του ιερέα πατέρα του, Γεωργίου, και επειδή γνώριζε γράμματα, χειροτονήθηκε στην εκκλησία «αναγνώστης». Ψηλός και σωματώδης καθώς ήταν, από Αναγνώστης μετονομάστηκε σε Αναγνωσταράς, αν και ο ίδιος υπέγραφε Αναγνώστης Παπαγεωργίου.Σε νεαρή ηλικία εξαιτίας μιας δολοφονίας έγινε κλέφτης.

Έπειτα, μετέβη στα Επτάνησα, όπου υπηρέτησε σε ρωσικά και γαλλικά τάγματα, και από εκεί τo 1817 στη Ρωσία όπου μυείται στη Φιλική Εταιρεία. Η μύησή του, μαζί με αυτή των Ηλεία Χρυσοσπάθη, Π Δημητροπούλου και Ι Φαρμάκη, θεωρήθηκαν από τις πρώτες θετικές επιτυχίες της Εταιρείας. Κατόπιν πραγματοποίησε περιοδείες σε διάφορα μέρη της Ελλάδας με σκοπό να προετοιμάσει τον αγώνα και να κατηχήσει νέα μέλη. Ανάμεσα σε αυτά ήταν ο Θεόδωρος Κολοκοτρώνης και ο Νίκος Παναγιωταράς.

Αργότερα, έγινε αρχηγός και αγωνίστηκε σε διάφορες μάχες και πολιορκίες στην Πελοπόννησο, όπως στην Καρύταινα και στο Βαλτέτσι. Στις 23 Μαρτίου 1821 εισέρχεται στην Καλαμάτα με τους Πετρόμπεη Μαυρομιχάλη, Θεόδωρο Κολοκοτρώνη, 2.000 Μανιάτες και άλλους αγωνιστές και συμμετέχει στην απελευθέρωσή της.

Ο Αναγνωσταράς είχε ενεργό ρόλο στον αγώνα. Τον Μάιο του 1821 συμμετέχει στην Συνέλευση Καλτεζών και τον Σεπτέμβριο του ίδιους έτους είναι μεταξύ των αρχηγών στην άλωση της Τριπολιτσάς. Στις 5 Μαΐου 1823, το Εκτελεστικό Σώμα της κυβέρνησης Κουντουριώτη τον διορίζει «Υπουργό του Πολέμου».