Альбом записывался в течение двух лет: с 2003 по 2005 годы и был выпущен на лейбле CD Land. В него вошли шесть синглов и три бонус-трека, одним из которых является ремикс на «Апельсиновую песню», записанный в девятом составе группы, в котором солировала Жанна Фриске. Заглавная песня альбома «Восточные сказки» была записана совместно с певцом Arash. Также в альбом вошла кавер-версия песни группы «Самоцветы» — «Налетели вдруг дожди».
За первые 6 месяцев в России было продано более 70.000 копий альбома, и около 100.000 копий в странах СНГ[источник не указан 3101 день].
Реакция критики
Виктор Шкурдюк из агентства InterMedia отметил на диске его заглавную композицию, в которой участницы группы «заигрывают с восточными мотивами и восточной же звездой тинейджерских журналов по имени Араш». Также он отметил и сингл «Пальмы парами». Однако по мнению рецензента, «малоизвестные пункты трек-листа с вероятностью в 95 процентов окажутся хуже своих раскрученных соседей по диску», и что «после шестого трека слушатель начинает скучать». Плюсом альбома автор рецензии посчитал композиции «Капитан дальнего плаванья», «Оперуполномоченный» и «Брат мой десантник», которые идут друг за другом. Рецензент посчитал это очень концептуальным, сказав, что «девичий квартет гарантировал себе дружбу с силовиками со всеми вытекающими последствиями в виде приглашений на шефские концерты».
