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....