Akcja powieści rozgrywa się w Marienburgu (Malborku) - siedzibie Krzyżaków oraz na Litwie ( w ojczyźnie tytułowego bohatera). Głównym i tytułowym bohaterem powieści jest tajemniczy (nie wiadomo, jak naprawdę się nazywał) Litwin. Kiedy był dzieckiem, na jego miasto napadli Krzyżacy, złupili je, jego rodziców zabili, a jego porwali. Wychowywał się u rycerza Diterycha von Kniprode, ale często przebywał w towarzystwie litewskiego wajdeloty (śpiewaka, poety, wieszcza), Halbana. Ten wpoił mu tożsamość narodową i nakłaniał do zemsty na prześladowcach Litwy. Bohater nosił wówczas imię Walter Alf.

W czasie jednej z bitew Walter i Halban przedarli się na stronę litewską. Tak przedostali się na zamek księcia Kiejstuta. Tu Walter opowiedział wszystko, czego zdołał się dowiedzieć o zakonie krzyżackim, a co mogło być pomocne w prowadzeniu walki: jego organizacji, uzbrojeniu, sposobach walki. Niestety było coraz bardziej oczywiste, że Litwa nie obroni się przed wrogiem.

Na zamku Kiejstuta Walter poznał jego córkę, Aldonę. Pokochali się i pobrali, ale kiedy stało się jasne, że w walce przeciwko Krzyżakom pozostały już tylko podstęp i zdrada, Walter nie wahał się poświęcić miłości do żony i własnego honoru. Opuścił Aldonę, i wrócił do zakonu, gdzie przedstawił się jako rycerz krzyżacki, Konrad Wallenrod. Aldona podążyła za nim, zamknęła się w wieży nieopodal Malborka i żyła jako pustelnica.

Po kilku latach Konrad Wallenrod został obrany wielkim mistrzem. Trzymał zakon żelazną ręką. Odwlekał, ile mógł, moment, w którym poprowadzi rycerzy zakonnych na śmierć i straci rycerski honor. Ostatecznie, pod naciskiem Halbana, który jako wajdelota znalazł się na zamku krzyżackim, Konrad wyrusza na wojnę z Litwą. Wprowadza zakonników w pułapki, przeciąga walkę, tak, że na polu bitwy zastaje ich sroga zima. Większość rycerzy ginie. Zakon jest zrujnowany, Litwa uratowana.

Niestety Konrad Wallenrod w tej walce również staje po stronie przegranych. Popełnia samobójstwo, w ślad za nim podąża Aldona - pustelnica.