Автору незабвенных «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» с булькающими ритмами и стихами, увлекающими в область бессознательного. Эту песню сочинила Бьорк. Она написала ее специально для Мадонны. Мадонне очень хотелось встретиться со знаменитой исландской певицей и, возможно, работать вместе, но та решила соблюдать дистанцию. «Я написала эту песню специально для нее, тем не менее интуиция подсказывала мне, что записывать ее вместе с Мадонной не стоит, — говорит Бьорк. — Я отказала ей в просьбе встретиться со мной. Если нам доведется познакомиться, пусть это произойдет случайно, например в баре, когда мы обе будем навеселе». Друзья Бьорк рассказывают, что она обеспокоилась, когда Мадонна начала сотрудничать с ее продюсерами и музыкантами: Хупером, Де Фрисом, Гаем Сигсвортом. На самом деле Бьорк настолько уникальна, что копировать ее никому не под силу.
Колоритный трек «Bedtime Stories» ознаменовал уклонение Мадонны в сторону электронной музыки. «Это был очень смелый выбор, хоть это и не кавер-версия Бьорк, у которой совершенно особенное построение фраз, — говорит Де Фрис. — Архитектура текста абсолютно бьорков-ская. Только самые отважные могут пытаться исполнить ее песни. Бьорковский язык очень трудно освоить, но Мадонна прекрасно справилась». Казалось, что, работая над песней, Мадонна открыла новые границы свободы. «Чтобы научиться другому языку, ей пришлось немного ослабить узду. „Bedtime Stories" был словно зародышем, из которого родились последующие альбомы», — считает Де Фрис.
Благодаря этой песне популярность Мадонны в Европе начала набирать обороты. В то время как в американских чартах сингл «Bedtime Stories» не достиг даже сорокового места, в Англии он быстро вошел в пятерку лучших и стал модным танцевальным шлягером, из которого делали ремиксы Джуниор Васкез и «Orbital». Она также вдохновила режиссера Марка Романека на создание одного из самых дорогих ее клипов (на съемку было потрачено пять миллионов долларов). В психоделическом фильме, снятом в стилистике Дали, Мадонна парит в воздухе, производит на свет голубей, лежит на операционном столе, при этом ее глаза и губы смещены, как у персонажей Фриды Кало. Видеоклип на песню «Bedtime Stories», автор которого самым очевидным образом вдохновился картиной Ремедиос Варо «Влюбленные», был расценен как образец высокого искусства, демонстрировался в художественных галереях и пополнил постоянную коллекцию лондонского музея кино.
Похоже, сотрудничество с Нелли Хупером несколько изменило эстетическое восприятие Мадонны. Ей так нравились записанные им треки, что она попросила его сделать ремиксы некоторых других песен, например «Sanctuary» и «Forbidden Love». «Ей нравилась его уверенная манера построения ритма и чувство пространства, — объясняет Де фрис. — Ей нравится внимание к деталям и профессионализм. Если вы обладаете этими качествами, она непременно это оценит».
Де Фриса поразил тот факт, что на запись и микширование пяти треков ушло всего две с половиной недели. «Это поразительно. Меня удивила скорость работы, при таких темпах приходилось проявлять решимость. Нужно было принимать серьезные решения и стараться не критиковать себя. Работа требовала значительной концентрации. Например, „Forbidden Love" мы сделали за две недели. Чтобы работать в таком темпе, нужно настраивать мозги особым образом. Я сочинял нечто приблизительно похожее на то, как все должно звучать, после чего она быстренько записывала голос. Мадонна почти всегда уверена в том, что делает». Для сравнения, «U2» записывали альбом по два года и «не принимали окончательных решений до самой последней минуты. У них совершенно другой подход: они делают черновик, который потом правят и правят. Мадонна работает по-хичкоковски: „Я снимаю только то, что считаю нужным"».