Далеко не сразу сложился окончательный композиционный план оперы. Мысль о сочинении былины возникала у Римского-Корсакова неоднократно. "Садко” как оперный сюжет, — упоминает композитор в "Летописи”, — занимал меня по временам несколько раз еще в восьмидесятых годах”. Летом же 1894 года во время работы над "Ночью перед рождеством" сложился и первоначальный план оперы-былины. Как указывает сам композитор, "конечно, сочинение "Ночи перед рождеством" было у меня на первом месте; тем не менее, тогда же мне пришли в голову некоторые новые музыкальные мысли и для "Садко", например, мелодия арии Садко, тема былины Нежаты, кое-что для финала оперы. Помнится, местом для сочинения такого материала часто служили для меня длинные мостки с берега до купальни в озеро. Мостки шли среди тростников; с одной стороны виднелись наклонившиеся большие ивы сада, с другой — раскидывалось озеро Песно. Все это как-то располагало к думам о "Садко". Примечательно само описание обстановки, в которой пришли к композитору первые музыкальные мысли для "Садко", здесь же в течение летних месяцев 1895 — 1896 годов опера была написана. Восторженное восприятие природы композитором подтверждает и следующий отрывок из "Летописи": "Имение Вечаша — прелестное место: чудесное большое озеро... Огромный старинный сад с вековыми липами, вязами... Ночью луна и звезды чудно отражаются в озере. Птиц множество... Лес поодаль, но прекрасный". Образы природы часто служили Римскому-Корсакову побудительным стимулом, вдохновляли его на создание прекрасных творений, словно пронизанных живительным теплом солнечного света, чарующе странными лунными бликами, отражающимися в зеркальной глади воды, завораживающим шелестом волшебного леса.
Вполне закономерно, что, преклоняясь перед чудесным ликом природы, Римский-Корсаков предлагал сосредоточить действие оперы на раскрытии фантастических эпизодов былины: плавании Садко по синему морю, его приключениях на дне морском, оставляя тем самым в стороне описание сцен из жизни Великого Новгорода. В. В. Стасов же, принявший самое активное участие в работе над сценарием, в письмах к Николаю Андреевичу писал: "Вы — новгородец; былина о Садке лучшая и значительнейшая былина новгородская... Я всей душой желал бы, чтобы вы... чудно изобразили бы не только личность Садко, но и вместе с тем дали бы по возможности наиполнейшую картину древнего Великого Новгорода со всем его характером — независимым, сильным, могучим, капризным, свободолюбивым, непреклонным и страстным". Римский-Корсаков не сразу согласился со сценарием, предложенным ему Стасовым. В ответном письме композитор указывал: ”Признаюсь, меня новгородские споры и партии очень мало привлекают, а влечет меня фантастическая часть, а также бытовая лирическая, и вот мне пришло на ум взяться за Садко, а о возможно полной картине Новагорода Великого я и не думал”. Однако сам жанр былины, включающий в себя элементы не только волшебно-фантастические, но и общеисторические, требовал воспроизведения хотя бы в обобщенном плане сцен из жизни новгородцев. И позже при составлении окончательного плана либретто, написанного Римским-Корсаковым совместно с В. И. Бельским, который сыграл особенно значительную роль в литературном оформлении либретто, композитор отчасти учел замечания Стасова и ввел в оперу ряд новых сюжетно-драматургических мотивов в первой, четвертой и седьмой картинах, а также еще одну героиню — Любаву Буслаевну, жену Садко (третья картина). В предисловии к первому изданию Римский-Корсаков отмечает, что действие ”Садко” происходит ”в полусказочную, полуисторическую эпоху только что водворившегося в Новгороде христианства, когда старые языческие верования были еще в полной силе”. Композитор не стремится при этом к исторической достоверности, конкретности, а передает в условной обобщенной манере облик русской старины, что свойственно былинному жанру. Таким образом, постоянное переплетение и взаимодействие двух планов — реального и фантастического, ”седой языческой древности” и ”элемента волшебного, сказочного”, по выражению Стасова, определило процесс сюжетно-музыкального развертывания материала этой эпической оперы, продолжающей собой традиции ”Руслана и Людмилы” Глинки и ”Князя Игоря” Бородина — ярчайших творений национального эпического музыкального театра.