В том же 1831 году в печати появились три крупных произведения Вельтмана: поэмы «Беглец» и "Муромские леса" и повесть «Странник». Форма повести была необычна, она состояла из отдельных фрагментов, написанных то стихами, то прозой, в ней не было сюжета, отрывочные картины, зарисовки перемежались рассуждениями, цитатами, историческими справками. Повесть вызвала у современников некоторое удивление.
Пушкину же повесть поправилась. "В этой несколько вычурной болтовне, — писал он, — чувствуется настоящий талант".
В своем творчестве Вельтман выступает как романтик. Герои его произведений — яркие, красочные персонажи, с необычной судьбой, их жизнь полна приключений, это излюбленные герои романтиков — разбойники, авантюристы, беглецы, то есть люди, нарушающие размеренный ход бытия.
Повествование Вельтмана часто приобретает фантастический характер, появляются привидения, случаются таинственные события. Как и все романтики, он интересуется фольклором, по мотивам русских сказок пишет роман "Кащей Бессмертный". Для Вельтмана характерно соединение стихов и прозы в одном произведении, в этом он следует форме фольклорных повествовательных жанров: сказки, народного рассказа и повести, в которых прозаический текст в драматических местах прерывается стихотворными монологами и песнями героев.
Одна из песен, сочиненная Вельтманом для героя его повести "Муромские леса", стала поистине народной; это песня "Что отуманилась, зоренька ясная".
В 1837 году Вельтман издал свой перевод "Слова о полку Игореве". Пушкин в заметке "Слово о полку Игореве" несколько раз ссылается на этот перевод.