В прозаическом предисловии к поэме автор замечает, что описывает те давние времена, когда язычники-литовцы сражались с главным врагом своим — Тевтонским орденом, покорившим Пруссию.
1391 г. В Мариенбург съезжаются рыцари, чтобы избрать главу ордена. Чаще других произносят здесь имя Валленрода — чужеземца, подвигами своими прославившего орден по всей Европе. «Не только грозной воинской отвагой он возвеличил званье крестоносца: но, презирая жизненные блага, он в христианской доблести вознесся». Рыцарь этот «своего оружия и чести не продавал враждующим баронам. В монастыре, соблазнов не касаясь, чуждаясь света, он проводит юность: ему чужды и звонкий смех красавиц, и песен менестрелей сладкострунность».
У человека этого, не старого годами, но мрачного, седого и бледного, есть единственный друг — святой монах Хальбан, его всегдашний исповедник.
Иногда Конрад поет песню на неведомом языке, и в глазах у рыцаря стоят слезы, а дух улетает в край воспоминаний. И нет в этой песне ни веселья, ни надежды...
А в башне замка живет затворница младая. Лет десять назад пришла она неведомо откуда в Мариенбург и «в башню добровольно заключилась. Теперь из высокого оконца затворница взывает: «Конрад! <...> Магистром став, твой долг — их уничтожить!»
Рыцари, слыша эти слова на незнакомом языке, понимают лишь имя «Конрад». Это «неба указанье», провозглашает Хальбан, и Конрада избирают великим магистром.
Все надеются, что Валленрод скоро покорит Литву. Но он «обычай предков дерзко нарушает»: призывает рыцарей отказаться от воинской славы и богатства. «Да будет добродетель нашей славой!» А у стен замка уже рыскают литвины. Конрад же по ночам ходит к башне и тихо переговаривается с затворницей. Она поет, как обратил ее, красавицу язычницу, рыцарь-христианин в свою веру и увлек в чужую страну. Конрад страдает: зачем несчастная последовала за ним?! Но она, потрясенная дерзким планом Конрада — «в немецком замке тайно появиться и, / местью поразив их стан немецкий, / за горести народа расплатиться», — хотела быть поблизости от любимого. Валленрод упрекает затворницу: когда-то он, горько плача, расстался с ней — и со своим счастьем — «для замыслов кровавых и мятежных». И вот теперь, когда он готов наконец отомстить «врагам заклятым», ее появление подорвало его силы. Хальбан осыпает Конрада упреками. Валленроду надо выступать в поход, а он не может покинуть любимую.
Конрад пирует с Витольдом, который, борясь за власть в Литве, пришел просить помощи у ордена. Старый литвин поет песню, срамя предателей, переметнувшихся к немцам. Устыдившись, Витольд «плащом закрылся и в черное раздумье погрузился». Старик же рассказывает о юном литвине, которого ребенком захватили в плен немцы, нарекли Вальтером Альфом и сделали крестоносцем. Великий магистр Венрих любит его, как родного сына. Но в литовском сердце скрывалась тоска по отечеству, ненависть к немцам. Юноша сходится со старым певцом-литвином; тот рассказывает сироте об отчизне и разжигает в нем ненависть к ее врагам. Старик велит юноше: «Оставайся у немцев, / учись у них ратному делу / и входи к ним в доверье...» Но в первом же бою с литвинами юноша устремляется к соплеменникам и рассказывает свою историю князю Кястуту и его дочке, «божественно юной» Алдоне. Вскоре молодые люди влюбляются друг в друга, и князь женит их. Но Вальтер, «благородный душою, не был счастлив в семье, / так как не было счастья в отчизне». Немцы наступают, и Вальтер боится, что они захватят всю Литву. Освободив Алдону от брачного обета, он тайком уходит к немцам, чтобы разрушить орден изнутри.
После пира Витольд изменяет союзникам-немцам, его люди громят немецкие замки. Конрад вынужден вести жаждущих мести крестоносцев в Литву. Возвращается он зимой с остатками разбитой армии. Знаменитый полководец Валленрод погубил на этот раз все свое войско. Лицо великого магистра мрачно, но глаза сияют.
В подземелье собирается тайный совет ордена. Один из двенадцати судей в масках заявляет, что граф Валленрод отправился когда-то в Палестину и вскоре пропал, а некий рыцарь из его свиты, прибыв в Испанию, назвался именем своего господина, которого, видимо, убил. Прославившись в Испании, где отважно громил он мавров, самозванец явился в Мариенбург. Двенадцать судей в черном единогласно выносят изменнику смертный приговор.
Исполнивший клятву Альф спешит к Алдоне. Он больше не хочет мстить — «немцы тоже люди» — и зовет любимую в Литву, чтобы начать жизнь сначала. Но поздно! Постаревшая Алдона не решается показаться мужу на глаза. Вскоре Альф слышит за своей спиной крик: «Горе, горе, горе!» Так тайный совет призывает приговоренных готовиться к смерти. Альф прощается с Алдоной. Ночью убийцы ломятся в его покой, и рыцарь осушает чашу с ядом. А старый Хальбан остается жить, чтобы всем рассказать о подвиге героя. «Одним ударом стоглавую я уничтожил гидру!» — гордо говорит Альф ворвавшимся к нему рыцарям и умирает. Увидев, что в оконце его погасла лампа, с воплем падает замертво в своей башне Алдона.
В «Объяснениях» Мицкевич отмечает, что Валленрод действительно поставил орден на грань гибели и сам умер при весьма загадочных обстоятельствах. Не был ли он тем немецким рыцарем Вальтером фон Стадионом, который, попав в плен к литовцам, женился на дочери Кястута и тайно уехал с нею из Литвы?