シャガールのような絵といえば、渡辺藤一さんかなあ？
それなら、文章は立原えりかさんかな？
というわけで、
かなりヤマカンなんですけど、
この本はどうですか？

『北欧幻想～白夜のメルヘン』
立原えりか　著
渡辺藤一　絵
講談社

私は未読ですので、確信はないのです。
調べてみると、メロディーブックと書かれていて、開くと音楽が流れる本のようです。
http://www.amazon.co.jp/gp/product/4061879111/

復刊リクエストにエントリーされています。
http://www.fukkan.com/fk/VoteDetail?no=13292

洛陽様、教えていただき、ありがとうございます。
絵を書いた渡辺藤一さんで調べてみたところ、この方の絵はとても素敵ですが、どうも記憶している絵とは違うようです。もっと思い出してみると、日本の作家の本ではなく、外国の作家の本の翻訳もので、児童書でした。短編集で、ほとんど若い女性が主人公、たぶんそれが王女とかそういった身分の人たちで、何か魔法にかけられて試練を与えられ、遠いところまで旅に出たりする。そこに動物がからんできていて、動物の力で魔法が解けたりすることもある。そのような内容だったと思います。若い女性が試練を与えられてもそれを皆受け入れて動物やその他の人々の力を借りて試練をこなしていく、といったことがとても美しい絵とともに描かれていた、という感じです。しかし、今から４０年近く前の、小学校中学年ぐらいの時に読んだものなので、うろ覚えとのところもあります。

並木道様、こんにちは！

具体的なタイトルではないので恐縮ですが、回答が出ないようなので、少しでも参考になればと思い・・・。

王女や王子が試練を課せられ（多くの場合は魔法が絡んでいて）、それを動物が助けて・・・というのは、ヨーロッパの民話や伝説に非常に多いパターンです。40年ぐらい前といえば、ロシア民話をベースにした絵本や童話集がよく出ていました。　そのあたりからお探しになってはどうでしょうか？
ご参考までに、wikiにロシア民話のページがあったので、貼り付けておきます。代表的な民話のあらすじが載っています。



参考URL:http://ja.wikipedia.org/wiki/Category:%E3%83%AD%E3%82%B7%E3%82%A2%E3%81%AE%E6%B0%91%E8%A9%B1