There's another starting formula of Russian folk tales:
Жили-были дед да баба...
Жили-были старик со старухой....
В тридевятом царстве, в тридесятом государстве жил-был старик и было у него три сына...