Приготовив все для поездки, запасшись официальными бумагами, которые должны были открыть ему вход во все архивы, Строев в мае 1829 г. выехал из Москвы к берегам Белого моря. Слишком долго было бы излагать любопытнейшие подробности этой экспедиции. Лишения, трудности сообщений и самой работы, убийственные гигиенические условия жизни и труда, болезни, подчас недоброжелательство и подозрительность невежественных хранителей архивов и библиотек, – все это стоически вынес Строев. Всего себя отдавал он работе, часто удивительно трудной и сухой, и лишь изредка, пользуясь отпусками для отдыха на какой-нибудь месяц, возвращался к своей семье. Утешительно то, что в этих трудах он нашел себе достойного помощника в лице Як. Ив. Бередникова (1793-1854), которым он в 1830 г. и заменил прежних чиновников. Энергия этих двух тружеников достигла чудесных результатов; пять с половиной лет трудились они, изъездив всю северную и среднюю Россию, осмотрели более 200 библиотек и архивов, списали до 3000 историко-юридических документов, относящихся к XIV, XV, XVI и XVII вв., обследовали массу памятников летописного и литературного характера. Собранный ими материал, будучи переписан, занял 10 огромных фолиантов, а в их черновых портфелях осталась масса справок, выписок и указаний, которые позволили Строеву составить два замечательных труда, появившихся в печати уже после его смерти. (Это «Списки иерархов и настоятелей монастырей Российской церкви», всех, которых помнит история, и «Библиологический словарь или алфавитный перечень всех рукописей исторического и литературного содержания», какие только Строев видел на своем веку.)
За путешествием Строева следила вся образованная Россия. Ученые обращались к нему, прося выписок, указаний и справок. Сперанский, готовя тогда в печать «Полное Собрание Законов Российской Империи», обращался к Строеву за помощью в собирании указов. Ежегодно, 29 декабря, вдень годичного заседания Академии наук, между прочим, читались отчеты и о действиях археографической экспедиции. Сведения о ней помещались в журналах. Император Николай прочитывал «от доски до доски» большие томы переписанных набело актов, собранных экспедицией.
В конце 1834 г. Строев был близок к окончанию своего дела. Северная и средняя поездки его были окончены. Оставалась самая меньшая – западная, т. е. Малороссия, Волынь, Литва и Белоруссия. В своем отчете Академии за 1834 г. Строев с торжеством заявлял об этом и, перечисляя результаты археографической экспедиции за все время ее существования, говорил: «От благоусмотрения Императорской Академии наук зависит: а) продолжать археографическую экспедицию в остальных областях Империи, дабы утвердить решительно: более сего нет, т. е. нет неизвестного материала, или б) начать печатание актов историко-юридических, почти приготовленных, и собрание разных писаний (т. е. летописных) по моим указаниям…» Этот отчет Строева читался в торжественном собрании Академии 29 декабря 1834 г., и почти в тот же день Строев узнал, что волей начальства (не Академии) археографическая экспедиция прекратила свое существование, что для разбора и издания добытых Строевым актов при Министерстве народного просвещения учреждена Археографическая комиссия. Строев был назначен простым членом этой комиссии наравне с своим прежним помощником Бередниковым и еще двумя лицами, к экспедиции вовсе не причастными