W "Przedmowie" narrator krótko prezentuje historię średniowiecznej Litwy. We "Wstępie" przedstawia genezę konfliktu krzyżacko-litewskiego, zapowiada rychłą wojnę. W Marienburgu, stolicy państwa Zakonu Krzyżackiego, odbywa się zgromadzenie komturów, którzy mają obrać swojego nowego Wielkiego Mistrza, przywódcę zakonu. Zostaje przedstawiony jeden z kandydatów, cudzoziemiec Konrad Wallenrod, który nigdy nie przegrał żadnego turnieju, ale lubi samotność i jest bardzo zamknięty w sobie. Przed udaniem się na spoczynek obradujący modlą się do Ducha Świętego i Chrystusa, aby dopomógł im we właściwym wyborze.
Arcykomtur, wraz zaufanymi braćmi i starym mnichem Halbanem kilka godzin spędzają poza zamkiem na spacerze i rozmowach dotyczących kandydatów. Gdy wracając już do domu przechodzą koło wieży nad jeziorem, w której zamurowana jest Pustelnica. Słysząc strzępy jej słów, wypowiadane do niewidzialnego rozmówcy, Halban interpretuje je jako dobrą wróżbę dla Wallenroda. Zakonnicy wracają do zamku z przekonaniem, że oto wybrali nowego przywódcę.
Mimo przysięgi, którą Konrad Wallenrod składa zostając Wielkim Mistrzem, wzbrania się przed rozpoczęciem wojny z Litwinami, którzy grabią nadgraniczne wsie i pustoszą okolicę. Mimo niezadowolenia zakonników, twardą ręką powstrzymuje ich od walki.
Okazuje się, że wieczorami Konrad wymyka się z zamku i długo rozmawia z Pustelnicą. Dzięki takiej rozmowie poznajemy historię ich miłości i nieszczęście rozstania.
Uczta na zamku, wyprawiona dla znamienitych gości, wśród których jest książe litewski, Witold, sprzyja biesiadnym nastrojom. Stary litewski wajdelota (pieśniarz) śpiewa wówczas "Pieśń Wajdeloty", w której zapowiada nadejście wielkiego męża, który oswobodzi Litwę. Następna w kolejności jest "Powieść Wajdeloty", opowiadająca o losach litewskiego dziecka porwanego przez Krzyżaków, wychowanego przez nich pod nazwiskiem Walter Alf. Mały Walter poznaje litewskiego wajdelotę, który był tłumaczem w krzyżackim wojsku. Pieśniarz opowiada mu o jego dziedzictwie i namawia do zemsty na Niemcach. Walter zostaje więc teutońskim rycerzem, a kiedy dochodzą go słuchy o planowanej wojnie, rusza wraz z wajdelotą do księcia Kiejstuta, na Litwę, by ostrzec swych braci. Tam zakochuje się w książęcej córce, Aldonie. Książe daje mu rękę córki, ale wymaga od niego, by walczył za Litwę. W nadchodzącej wojnie obaj walczą ramię w ramię, jednak wiedzą, że nie skruszą potęgi zakonu. Podejmują zatem jakiś szaleńczy plany, który wymaga od Alfa, by porzucił świeżo odzyskaną ojczyznę i ukochaną żonę. "Powieść..." kończy się sceną rozstania kochanków, po której wajdelota przerywa pieśń. Zgromadzeni chcą posłuchać do końca, ale Konrad zabiera lutnie i sam wykonuje swoją balladę. To z pozoru inna historia, ale tak naprawdę świetnie pokazuje dalsze losy Alfa. Mistrz śpiewa "Balladę Alpuhara", pieśń o oblężeniu twierdzy, dowodzonej przez Almanzora, króla muzułmanów. Król poddał się oblegającym, zapowiedział że chce się im pokłonić i oddać cześć ich Bogu. Przyjęto go serdecznie, a gdy wszystkich wyściskał i wycałował, padł na ziemię i zapowiedział rychłą śmierć, przywiózł bowiem zarazę z Grenady.
Uczta kończy się w nie najlepszych nastrojach, nikt bowiem nie wie jak interpretować pieśń i zachowanie Mistrza, oraz gniew Witolda, któremu Konrad zarzucił, że oddaje swoje ziemie jak Almanzor.
Litwini ponownie najeżdżają ziemie Zakonu i tym razem nie daje się już powstrzymać wojny. Konrad prowadzi jednak wojsko do boju tak nieudolnie, że wraca z bitwy ledwie z garstką rycerzy. Bracia zakonni zawiązują spisek, dowiadują się bowiem o przeszłości Konrada, który jest właśnie Walterm Alfem z "Powieści wajdeloty". Skazują zatem swojego Mistrza na śmierć.
Alf odwiedza Pustelnicę-Aldonę i prosi, żeby uciekła z nim na Litwę, opowiada o ciosie, jaki zadał Zakonowi. Jednak jego żona odmawia, bojąc się pokazać ukochanemu po tylu latach. Zrozpaczony rycerz zażywa w swej komnacie truciznę. Kiedy przychodzą po niego bracia chcący go uwięzić, jest już bardzo słaby, lecz staje przed nimi z mieczem w dłoni. Ostatkiem sił strąca z okna lampę i umiera. Ciszę rozdziera krzyk Aldony, która widząc gasnące światło wie, że oznacza to śmierć jej męża. Umiera ona z rozpaczy.