Мадонна чрезвычайно щепетильна в вопросах этики. Когда дело дошло до исполнения «Take A Bow», она проследила, чтобы Бэйбифэйс стоял рядом с ней. «На репетициях он обычно стоял позади нее, на помосте, а тут она поставила его рядом с собой, как бы подчеркивая, что они вместе. Это было данью уважения. Такое внимание редкость», — говорит Херц.
Бэйбифэйс познакомил Мадонну с молодым талантливым продюсером Далласом Остином, который делал песни для «TCL» и был хорошо известен в музыкальных кругах. Их сотрудничество обернулось появлением на свет двух лучших песен альбома: «Secret» и «Sanctuary». В плотном по ритму, с деликатной струнной секцией и задушевной гитарной мелодией треке «Secret» одновременно сочетались расслабленность и напряжение. Песня похожа на откровение души. Мадонна утверждала, что она не столько про любовь, сколько об обретении веры в себя: «Эта песня о Боге, не о том, который сидит на небесном престоле, а о том, который живет внутри каждого из нас». Композиция «Secret» — переработанный оригинал петтибоновской «Something's Coming Over Me». Даллас заставил голос Мадонны звучать нежнее и глубже и сделал ее эротическое мычание выгодным штрихом песни. В медитативном треке «Sanctuary» Мадонна размышляет о любви, в которой ищет забвения и успокоения, вплетая в бессознательные мечты библейские апокалиптические образы.
Композицию «Human Nature», одну из самых оригинальных в альбоме, Мадонна выпустила совместно с продюсером Мэрайи Кэри Дэйвом Холлом. Она была темпераментным ответом всем критикам книги «Секс» — переполняющий Мадонну гнев выражен звуком хлопающей двери, также для записи трека использовался семпл из композиции «What You Need» группы «Main Source». Черно-белый клип, снятый на эту песню, отражает ее тогдашнее состояние загнанного в клетку зверя. Мадонна показана пленницей замкнутых помещений: психиатрических палат, тесных комнат. Видеоредактор Дастин Робертсон рассказывает, как он работал ассистентом Жан-Батиста Мондино на съемках этого видео. «Я тогда впервые познакомился с Мадонной. Она вышла из трейлера в кожаном костюме и сапогах на шпильках. Мадонна аккуратно ступала по сцене, стараясь не задеть электрические провода и коробки, разбросанные по полу. Воцарилась тишина. Она произвела на меня ошеломляющее впечатление».
Автору незабвенных «Open Your Heart» и «Justify My Love» Мондино и в этот раз удалось преподнести Мадонну именно так, как ей хотелось. «У них абсолютно разная энергетика, поэтому то, что они делают вместе, получается просто здорово, — говорит Робертсон. — Она часто придирается, а он на все реагирует спокойно. Он сильный человек и знает, как с ней обращаться. С ней нужно быть требовательным, она любит „дрессировщиков"». Поклонники Мадонны не сумели оценить ни превосходно сделанную песню, ни бесподобный клип. В чартах журнала «Billboard» сингл «Human Nature» занял лишь 4б-е место.
Мадонна предприняла некоторые смелые музыкальные шаги совместно с Дэйвом Холлом, результатом явилась песня «I'd Rather Be Your Lover». В ее записи приняла участие исполнительница неосоула Ми'Шель НдегеОселло, коротко стриженная бас-гитаристка и автор-песенник нетрадиционной сексуальной ориентации. Она оказалась одним из первых музыкантов, кто заключил контракт с «Maverick». НдегеОселло познакомилась с Мадонной благодаря Андре Беттсу, и та незамедлительно предложила ей записываться на своем лейбле. Ее дебютный альбом под названием «Plantation Lullabies» проложил дорогу новому соул-движению 90-х, которое возглавляли такие певицы, как Индиа Ари и Эрика Баду. НдегеОселло использовала плантацию в качестве метафоры для описания современного гетто. «Мои колыбельные — это затишье перед революционной бурей, которую вскоре поднимут цветные народы». НдегеОселло не была столь же успешной, как Аланис Мориссетт, которая записывалась на «Maverick» несколько позднее, но все же она послужила лейблу хорошей рекламой.
Спеша утвердиться на расцветающем соул-рынке, Мадонна несколько не рассчитала свои вокальные возможности. В тот период ее голос был недостаточно гибок и силен для исполнения столь сложного жанра. В «Bedtime Stories» он иногда звучит неуверенно, Мадонна будто пробует себя в новом качестве соул-певицы. Испытывая потребность разнообразить альбом, она обратила взор на Британию, где на музыкальную арену вышли такие исполнители, как Бьорк, «Massive Attack» и «Soul 2 Soub, Продюсером этой впечатляющей троицы был Нелли Хупер. «У него чисто европейское музыкальное чутье, которое я очень ценю», — отметила Мадонна и привезла его в Лос-Анджелес.
Так Мадонна начала сотрудничать с английскими музыкальными экспериментаторами — электронная аранжировка очень хорошо подошла ее голосу. Наряду с Нелли Хупером Мадонна выписала из Британии его помощника, программиста и продюсера Мариуса Де Фриса. «Мне всегда было интересно возиться с синтезатором и экспериментировать со звуками», — говорит Де Фрис, бывший певчий собора Святого Павла и любитель регги, в начале 90-х активно сотрудничавший с Бьорк. В итоге и без того немалочисленный список продюсеров «Bedtime Stories» пополнился двумя новыми именами.
«В проекте участвовало рекордное количество продюсеров. Нам с Нелли приходилось считаться с тем, что было сделано до нас, чтобы добиться языкового единообразия», — говорит Де Фрис. Мадонне хотелось, чтобы альбом был цельным и не походил на сборную солянку. Некоторые считали, что на ее музыкальной кухне и так уже побывало слишком много поваров. «Это не так, потому что повара не были в помещении одновременно, — возражает Де Фрис. — Но нужно было стараться не смещать фокус. Не думаю, что продюсеры потратили много времени на обсуждение альбома друг с другом. Вся ответственность лежала на Мадонне, и, надо отдать ей должное, он получился довольно гармоничным».
Хупер и Де Фрис приступили к работе над альбомом тем же летом, в калифорнийской студии «ChappeLL», в Энсино.
В первый день записи Де Фрис принял Мадонну за уборщицу. «Я пришел на студию рано, чтобы подготовить аппаратуру. Забыл надеть контактные линзы, и мне все виделось несколько смазанным. Я расположился, начал включать свои приборчики, а в углу сидела какая-то девушка. Я панибратски поздоровался с ней, продолжая заниматься своими делами. Никак не думал, что Мадонна придет так рано. На выяснение этого недоразумения ушло полчаса, — улыбается Де Фрис. — Она была очень любезна, не рассердилась на меня и даже наоборот, развеселилась. У нее есть чувство юмора».
Хупер записал три трека альбома «Bedtime Stories». Первой была записана композиция «Survival» — яркая, праздничная песня, отражающая состояние души Мадонны. Следом за ней появилась «Inside Of Me», песня о любви, исполняемая от лица уязвимой и гордой девушки, в которой поется о том, что нужно сохранять достоинство, невзирая ни на что. Последним был минималистский трансовый трек «Bedtime Stories» с булькающими ритмами и стихами, увлекающими в область бессознательного. Эту песню сочинила Бьорк. Она написала ее специально для Мадонны. Мадонне очень хотелось встретиться со знаменитой исландской певицей и, возможно, работать вместе, но та решила соблюдать дистанцию. «Я написала эту песню специально для нее, тем не менее интуиция подсказывала мне, что записывать ее вместе с Мадонной не стоит, — говорит Бьорк. — Я отказала ей в просьбе встретиться со мной. Если нам доведется познакомиться, пусть это произойдет случайно, например в баре, когда мы обе будем навеселе». Друзья Бьорк рассказывают, что она обеспокоилась, когда Мадонна начала сотрудничать с ее продюсерами и музыкантами: Хупером, Де Фрисом, Гаем Сигсвортом. На самом деле Бьорк настолько уникальна, что копировать ее никому не под силу.