Сценарий фильма написан по мотивам баллады Василия Жуковского "Сказка о царе Берендее, о сыне его Иване-царевиче, о хитростях Кощея бессмертного, и о премудрости Марьи-царевны, Кощеевой дочери". В свою очередь её первоисточником стала народная сказка "Морской царь и Василиса Премудрая".
Авторами сценария были Михаил Чуприн и режиссёр Александр Роу - для Чуприна это была единственная работа в кино, а для Роу "Варвара-краса, длинная коса" стала предпоследним фильмом.Роу любил работать с уже знакомыми актёрами, так что почти все исполнители ролей снимались у него в предыдущих фильмах. Исключением стала Татьяна Клюева, сыгравшая Варвару - она у Роу снималась впервые, хотя познакомились они задолго до съёмок. Десятиклассница Клюева приходила на пробы к его предыдущей сказке "Огонь, вода и... медные трубы", но показалась режиссёру совсем ребёнком, хотя у неё уже был актёрский опыт и даже главная роль в фильме "Акваланги на дне". Роу утвердил Наталью Седых, а Клюевой пообещал снять её в следующей работе. И сдержал обещание - девушку пригласили на пробы уже через год.
Перед началом съёмок режиссёр строго предупредил 18-летнюю актрису: никаких романов, гулянок, сомнительных историй и лишних килограммов! В девять вечера Роу закрывал актрису в номере на ключ, а когда оказалось, что ей всё-таки малы подготовленные платья, режиссёр отказал "Варваре" в суточных, чтобы она не тратила их на булочки. Лишён суточных был и "подводный царь" Георгий Милляр - у него под запретом было спиртное. Это сплотило актёров и после того, как группа получала деньги, Милляр и Клюева шли к режиссёрам комбинированных съёмок, садились на лавочку и грустно вздыхали. Им тайком выдавали один рубль на двоих, актёры шли в соседнюю деревню и покупали "вкусности": Милляр - крепкое вино, а Клюева - конфеты или колотый сахар...
Роль Варвары принесла Татьяне Клюевой всесоюзную популярность, но осталась её самой яркой работой в кино. Актриса окончила ГИТИС, сыграла несколько ролей второго плана, а вскоре вышла замуж за моряка и уехала за ним в Севастополь. Там она заведовала клубом в таксопарке, работала в брачном агентстве, а в 90-е торговала одеждой и обувью на рынке. Сейчас Татьяне Клюевой 71 год, она по-прежнему живёт в Севастополе и до недавних пор работала в севастопольском отделении Союза кинематографистов.
На съёмках сказки Татьяна Клюева на всю жизнь подружилась с исполнителем роли царского сына Андрея. Режиссёр заметил колоритного вожатого в пионерском лагере киностудии им. Горького и пригласил на роль не менее колоритного "упитанного, но невоспитанного" Андрюшеньки-душеньки. Для Сергея Николаева это была вторая роль в кино, которая тоже стала самой яркой в фильмографии. Он окончил экономический факультет ВГИКа, 20 лет возглавлял актёрский отдел киностудии им. Горького и много снимался в ролях второго плана и эпизодах. Сергея Николаева не стало в 2016 году
Алексея Катышева, исполнителя роли рыбацкого сына Андрея, режиссёр уже снимал в предыдущем фильме. Пятнадцатилетнего Катышева он заметил на курсах звукорежиссёров на Ялтинской киностудии, ещё когда снимал "Морозко". Роу запомнил молодого человека, так как сказочнику всегда был нужен типаж русского доброго молодца с ярко-голубыми глазами. Через четыре года он без проб утвердил актёра в фильм "Огонь, вода и... медные трубы", а сразу после окончания съёмок предложил ему сняться в "Варваре-красе, длинной косе". Актёра к тому времени забрали в армию, но режиссёр добился его перевода с Дальнего Востока в Ленинград - поближе к съёмочной площадке.Алексей Катышев собирался продолжить карьеру, но через два года Александр Роу умер, а другие режиссёры интереса к нему не проявили. Катышев сыграл главную роль в "Весенней сказке", эпизод в детском фильме "Про Витю, про Машу и морскую пехоту" и на этом предложения закончились... Дальнейшая судьба актёра сложилась трагически - он работал водителем молоковоза и грузчиком, много пил, потерял семью и квартиру, едва не попал в тюрьму и скончался в 2006 году.
У Александра Роу было два любимых места для съёмок - Крым и окрестности подмосковного Звенигорода. Там снималась и "Варвара-краса, длинная коса" - часть работы прошла возле пионерского лагеря "Мирный" и в деревне Гигирево, а часть на Южном берегу Крыма, в Никитской расселине и у горы Ай-Петри. Сцены подводного царства снимали в павильоне киностудии им. Горького, где построили масштабные декорации.Администратором на съёмках сказки работал 20-летний Борис Грачевский, который учился во ВГИКе и попал на практику к Александру Роу. Он вспоминал, что решал нетривиальные задачи - ловил голубей или искал сухой лёд, а в конце съёмок сыграл роль руки... По задумке режиссёра из-под воды появлялась рука, которая грозила царю пальцем и голос произносил: "Должооок..." На площадке поставили огромный таз с водой и кому-то надо было нырнуть и надеть специальную перчатку с когтями. Грачевский был самым молодым членом съёмочной команды, поэтому руку поручили ему. Получился эпизод, который потом много лет пугал маленьких зрителей...