Стремление составителей «Калевипоэга» исторически осмыслить фольклорный материал, конкретнее и убедительнее выявить присущее народной поэзии свободолюбие столкнулось с мрачной действительностью последних лет царствования Николая I и пресловутым «остзейским особым порядком». Окончательное завершение эпоса совпало с революционной ситуацией в России в 1859–1861 годах и явилось в известной степени ее литературным отражением.
Начало собиранию многочисленных сказаний о Калевипоэге, встречающихся в эстонском устном народном творчестве, было положено Фельманом. Впервые об этом упоминается в его письме Крейцвальду в 1833 году. Именно Фельману принадлежит мысль о создании эпоса, возникшая у него, по всей вероятности, под влиянием выхода в свет в 1835 году первоначального издания карело-финского народного эпоса «Калевала», тем более, что уже раньше Петерсон указывал на общие мотивы в фольклоре двух родственных народов.
В 1838 году по инициативе Фельмана при Тартуском университете было создано Ученое эстонское общество по исследованию фольклора, языка и исторического прошлого эстонского народа; в члены этого общества вступил и Крейцвальд. В начале 1839 года Фельман на собрании общества прочитал доклад о результатах своей работы над сказаниями о Калевипоэге. Этот сжатый обзор явился первой попыткой объединить различные народные предания, связанные с богатырем Калевипоэгом, в идейно-тематическое целое. С тех пор Фельман постоянно занимался исследованием фольклорных материалов о Калевипоэге. У него возникла даже мысль отказаться от врачебной деятельности и по примеру составителя «Калевалы» Э. Лённрота собирать по стране материалы о Калевипоэге. Однако эти планы не были осуществлены из-за преждевременной смерти Фельмана, последовавшей в 1850 году. Работу над составлением «Калевипоэга» продолжил Крейцвальд.
Опираясь на распространенные в то время теории, составители «Калевипоэга» считали, что эпос некогда бытовал в народе как нечто целое, а с течением времени распался на фрагменты и частично позабылся. С точки зрения общественных задач такое понимание давало составителям возможность подчеркнуть высокую древнюю культуру народа и его героическое прошлое и нанести этим прямой удар по идеологии феодализма. Крейцвальд видел свою задачу в том, чтобы на основе сохранившихся фрагментов и частей эпоса представить себе величественные контуры некогда единого целого, соединить весь имеющийся у него материал таким образом, чтобы произведение по возможности соответствовало предполагаемому древнему эпосу.
Сейчас, на основе сравнительного исследования, мы знаем, что эта теория о целостных эпосах, бытовавших в прошлом в народе, не имеет под собой почвы. Появление целостных эпосов, начиная с времен античной Греции, всегда было результатом сознательной организации материала, большей или меньшей литературной обработки, подбора, объединения и слияния многочисленных вариантов. И это вполне закономерно, так как при устной передаче ни один, даже самый выдающийся народный певец-импровизатор не смог бы точно запомнить сказания и легенды, достигающие порой объема в десятки тысяч строк. Об эпосе, как о целостном произведении, можно говорить лишь тогда, когда он записан.
Разумеется, работа над составлением эпоса зависит от характера имеющихся материалов. Например, составитель карело-финского эпоса «Калевала» Лённрот мог использовать руны в их стихотворной форме, повествовавшие об отдельных приключениях героев. Составителю пришлось творчески обработать, объединить разрозненные истории в одно логическое целое, причем Лённрот значительно расширил руны за счет народного песенного материала — лирических песен, заклинаний и т. д. Несравненно более сложная задача стояла перед Крейцвальдом.
Взяв в основу эскиз эпоса, разработанный Фельманом, и использовав его записи, Крейцвальд и сам дополнительно собрал фольклорные материалы. Однако материал, которым он располагал, был недостаточен. Крейцвальд восполнял пробелы песнями и сказаниями, не имеющими непосредственного отношения к преданиям о Калевипоэге, и в некоторых случаях вносил отдельные литературные дополнения, на что он сам и указывал.
Предания о Калевипоэге бытовали в устном народном творчестве большей частью в форме прозаических повествований. Вначале у Крейцвальда было намерение весь материал, касающийся Калевипоэга, оформить в тематический сборник сказаний с вплетенными в них соответствующими народными песнями и фрагментами. Подготовив материал, Крейцвальд вскоре убедился, что этот труд не удовлетворяет его. Близкое знакомство с песенным богатством псковских эстонцев побудило Крейцвальда отказаться от первоначальной мысли и объединить весь материал в единое целое, обратившись к стихотворной форме эстонской народной песни. В 1853 году был закончен первый вариант «Калевипоэга», состоявший из двенадцати песен, как задумал еще Фельман.