Во вступлении автор вспоминает музыканта Навадагу, когда-то в старинные времена певшего песнь о Гайавате: «О его рожденье дивном, / О его великой жизни: / Как постился и молился, / Как трудился Гайавата, / Чтоб народ его был счастлив, / чтоб он шел к добру и правде».
Верховное божество индейцев, Гитчи Манито — Владыка Жизни, «сотворивший все народы», начертавший пальцем русла рек по долинам, слепил из глины трубку и закурил ее. Увидев поднимавшийся к небу дым Трубки Мира, собрались вожди всех племен: «Шли Чоктосы и Команчи, / Шли Шошоны и Омоги, / Шли Гуроны и Мэндэны, / Делавары и Могоки, / Черноногие и Поны, / Оджибвеи и Дакоты».
Гитчи Манито призывает враждующие племена примириться и жить «как братья» и предрекает появление пророка, который укажет им путь к спасению. Повинуясь Владыке Жизни, индейцы погружаются в воды реки, смывают боевую краску, закуривают трубки и пускаются в обратный путь.
Победив огромного медведя Мише-Мокву, Мэджекивис становится Властелином Западного ветра, другие же ветры отдает детям: Восточный — Вебону, Южный — Шавондази, Северный — злому Кабибонокке.
«В незапамятные годы, / В незапамятное время» прямо с месяца упала на цветущую долину прекрасная Нокомис, дочь ночных светил. Там, в долине, Нокомис родила дочь и назвала ее Веноной. Когда дочь выросла, Нокомис не раз предостерегала ее от чар Мэджекивиса, но Венона не послушалась матери. «И родился сын печали, / Нежной страсти и печали, / Дивной тайны — Гайавата».
Коварный Мэджекивис вскоре оставил Венону, и та умерла от горя. Гайавату вырастила и воспитала бабка. Став взрослым, Гайавата надевает волшебные мокасины, берет волшебные рукавицы и отправляется на поиски отца, горя желанием отомстить ему за гибель матери. Гайавата начинает бой с Мэджекивисом и вынуждает его отступать. После трехдневного сражения отец просит Гайавату прекратить бой. Мэджекивис бессмертен, его нельзя одолеть. Он призывает сына вернуться к своему народу, расчистить реки, сделать землю плодоносной, умертвить чудовищ, и обещает сделать его после смерти владыкой Северо-Западного ветра.
В лесной глуши Гайавата постится семь дней и ночей. Он обращается к Гитчи Манито с молитвами о благе и счастье всех племен и народов, и как бы в ответ у его вигвама появляется юноша Мондамин с золотистыми кудрями и в зелено-желтых одеждах. Три дня Гайавата борется с посланником Владыки Жизни. На третий день он побеждает Мандамина, хоронит его и затем не перестает навещать его могилу. Над могилой один за другим вырастают зеленые стебли, это иное воплощение Мандамина — кукуруза, пища, посланная людям Гитчи Манито.
Гайавата строит пирогу из березовой коры, скрепляя ее корнями тэмрака — лиственницы, делая раму из ветвей кедра, разукрашивает иглами ежа, окрашивает соком ягод. Затем вместе со своим другом силачом Квазиндом Гайавата поплыл по реке Таквамино и очистил ее от коряг и мелей.
Гайавата находит себе жену, прекрасную Миннегагу из племени дакотов. На свадебном пиру в честь жениха и невесты танцует красавец и насмешник По-Пок-Кивис, музыкант Чайбайабос поет нежную песню, а старый Ягу рассказывает удивительную легенду о волшебнике Оссэо, сошедшем с Вечерней Звезды.
Чтобы уберечь посевы от порчи, Гайавата велит Миннегаге во мраке ночи обойти поля обнаженной, и она послушно, «без смущения и без страха» повинуется. Гайавата же ловит Царя-Ворона, Кагаги, осмелившегося привести стаю птиц на посевы, и для острастки привязывает его на кровле своего вигвама.
Гайавата придумывает письмена, «чтоб грядущим поколеньям / Было можно различить их».
Страшась благородных стремлений Гайаваты, злые духи заключают против него союз и топят в водах Гитчи-Гюми его ближайшего друга музыканта Чайбайабоса. Гайавата от горя заболевает, и его исцеляют с помощью заклинаний и магических плясок.
Дерзкий красавец По-Пок-Кивис учит мужчин своего племени играть в кости и безжалостно их обыгрывает. Затем, раззадорившись и зная к тому же, что Гайавата отсутствует, По-Пок-Кивис разоряет его вигвам. Вернувшись домой, Гайавата пускается в погоню за По-Пок-Кивисом, а тот, убегая, оказывается на бобровой плотине и просит бобров превратить его в одного из них, только больше и выше всех остальных. Бобры соглашаются и даже избирают его своим вождем, и Гайавате удается справиться со своим врагом, только призвав на помощь молнию и гром.
Гайавата лишается еще одного своего друга — силача Квазинда, которого погубили пигмеи, попавшие ему в темя «голубой еловой шишкой», в то время как он плыл в пироге по реке.
Наступает суровая зима, и в вигваме Гайаваты появляются призраки — две женщины. Они мрачно сидят в углу вигвама, не говоря ни слова, лишь хватают лучшие куски пищи.
В селеньях индейцев начинается голод. Гайавата отправляется на охоту, но безуспешно, а Миннегага слабеет день ото дня и умирает. Гайавата, исполненный скорби, хоронит жену и четыре ночи жжет погребальный костер. Прощаясь с Миннегагой, Гайавата обещает скоро встретиться с ней «в царстве светлого Понима, / Бесконечной, вечной жизни».
В селенье возвращается из далекого похода Ягу и рассказывает, что видел Большое Море и крылатую пирогу «больше целой рощи сосен». В этой лодке Ягу видел сто воинов, лица которых были выкрашены белой краской, а подбородки покрыты волосами. Индейцы смеются, считая рассказ Ягу очередной небылицей. Не смеется только Гайавата.
Гайавата рассказывает, что Владыка Жизни открыл ему будущее: он видел «густые рати» народов, переселяющихся на Запад. «Разны были их наречья, / Но одно в них билось сердце, / И кипела неустанно / Их веселая работа: / Топоры в лесах звенели, / Города в лугах дымились, / На реках и на озерах / Плыли с молнией и громом / Окрыленные пироги».
Но открывшееся Гайавате будущее не всегда лучезарно: он видит и индейские племена, гибнущие в борьбе друг с другом.
Гайавата, а за ним и остальные индейцы приветливо встречают приплывших на лодке бледнолицых и приобщаются к истинам, которые провозглашает наставник бледнолицых, «их пророк в одежде черной», — к началам христианской религии, рассказам «о Святой Марии-Деве, / О ее предвечном Сыне».
Гости Гайаваты засыпают в его вигваме, истомленные жарою, а сам он, простившись с Нокомис и со своим народом и завещая внимать мудрым наставлениям присланных из царств света гостей, уплывает в своей пироге на Закат, в Страну Понима, «к Островам Блаженных — в царство / Бесконечной, вечной жизни!».