Ланг уважала Мадонну за волевой характер, но не одобряла ее поведения. К тому же, по ее мнению, техническая подготовка молодой танцовщицы оставляла желать лучшего. «Одно могу сказать: я вывела ее на сцену. В балете главное — подача движения. У некоторых все получается легко, другие берут приступом. Мадонна из второй категории. Но ничего плохого про нее сказать не могу. Конечно, были ученики и поталантливей, а ей, сами знаете, всегда нравилась попса. — Ланг усмехается в ответ на вопрос о влиянии Грэхем. — Ни в коем разе. Мы с Мартой не имеем к ее деятельности никакого отношения. Она же попсовая певичка».
Пережив психическую травму, устав от балетной муштры. Мадонна захотела сменить поле деятельности. Изнасилование сыграло роль курка, она как пуля понеслась к другой цели. Теперь самым привлекательным местом для нее была клубная танцплощадка, где она забывала о своих страхах.
Следующие несколько месяцев были непростыми. Мадонна продолжала танцевать, посещала занятия на Манхэттене и тренировалась дома, но без Ланг чувствовала себя неуверенно. Она познакомилась с художником Нор-рисом Берроузом, и у них начался роман, правда продлился он недолго. Это был период относительного спокойствия.
Они занимались любовью и ходили на прогулки. Берроузу нравилась природная дикость Мадонны. Ему казалось, что в ней есть что-то загадочное и непостижимое, что она словно «сотворена из света».
В 1979-м у Мадонны завязались отношения с начинающим музыкантом Дэном Гилроем. Дэн вместе с братом Эдом основал группу «Breakfast Club», исполнявшую музыку в стиле фанк-поп с примесью ска. Дэн и Мадонна познакомились в баре в Верхнем Уэст-Сайде. Был обычный будничный вечер, и почти никого народу. «Я — ведомый партнер. Она вертелась вокруг меня, забрасывая ноги к самой шее, выполняя пируэты, и все такое. Танцевать в пустом зале страшно и неловко, а она делала все так классно… с ней чувствуешь себя уверенно».
Вскоре после знакомства с Гилроем Мадонна получила предложение работать в Париже, танцевать в диско-ревю Патрика Хернандеза. Берроуз рассказывает, что Дэн с братом придумали маленький спектакль, который был частью водевиля под названием «Voidville». Им заинтересовались продюсеры Хернандеза Жан Ван Лье и Жан Клод Пеллерен. Через Дэна они вышли на Мадонну и уговорили ее попробовать себя в качестве солистки диско-шоу.
Она приехала во Францию, где Ван Лье и Пеллерен взяли над ней шефство, пытаясь сделать из нее нечто вроде танцующей Эдит Пиаф. Мадонну без конца приглашали на обеды, где обсуждались различные творческие проекты, которые почти никогда не реализовывались. Она привыкла много работать и нервничала из-за вынужденного простоя. Однако этот период был для нее переходным: она перестала быть «просто танцовщицей» и начала петь. В Париже 1979-го невозможно было избежать влияния «Мулен Руж» и модного диско. Хернандез со своим альбомом «Born То Be Alive» стал мегазвездой. Неудивительно, что в первых записях Мадонны сильно чувствуется влияние именно европейской поп-музыки. Париж того времени был глубокой провинцией в плане музыки, средоточием всей жизни были кафе. Мадонна посещала вечеринки, устанавливала полезные контакты и прониклась к этому городу любовью, которая впоследствии укрепится в процессе сотрудничества с Мирвайсом, Мондино и Жан-Полем Готье. «В семидесятых годах вся светская жизнь Парижа происходила в кафе, — вспоминает Мелинда Паттон, светская львица, проживавшая в Париже в то же самое время, что и Мадонна. — Там можно было встретить кого угодно. Все всё время тусовались. Вы идете встречаться с одним человеком и знакомитесь с миллионом других».
Мадонне нравилась светская жизнь, но она чувствовала, что в карьере наступил застой, и решила вернуться домой. Ей по-прежнему хотелось любой ценой добиться успеха, поэтому, увидев в журнале «Back Stage» объявление том, что для съемок некой кинокартины требуется женщина, умеющая танцевать и согласная работать бесплатно, она незамедлительно выслала свое резюме режиссеру Стивену Джону Левицки и была утверждена на роль. Фильм назывался «Определенная жертва», Мадонна там играла садомазохисту Бруну, которая бессмысленно шляется со своими дружками там и сям, покуда не встречает хорошего парня, который только и ждет, чтобы его совратили. Они сходятся, и Бруна, исполнившись раскаяния, рассказывает о том, как она втянулась в жестокую игру извращенных сексуальных отношений.
Бруну насилуют в туалете, после чего она умирает. Мадонне было нелегко играть эту сцену, она слишком живо помнила о собственном изнасиловании, поэтому на экране выглядит искренне напуганной. В фильме обидчику Бруны устраивают засаду и убивают под заупокойные звуки готического рока. Картина вышла неудачной, спасти неуклюжий сценарий и плохую игру актеров не смогли даже чувственность и эмоциональность Мадонны. К концу съемок у Левицки кончились деньги, и он закончил фильм лишь тогда, когда Мадонна уже стала знаменитой. Он вышел в прокат в 1985 году. Интересно, что в образе Бруны содержится то самое противоречие девственница-шлюха, которое Мадонна будет позднее исследовать в своем творчестве, как и тему наказания за открыто проявленную сексуальность.
В восьмидесятых годах Мадонна активно занялась музыкой. Она присоединилась к группе Гилроя — вместе с ним и его братом они оккупировали заброшенное здание синагоги в Квинсе. У Мадонны было хорошее чувство ритма, поэтому первые несколько месяцев она сидела за барабанной установкой и лишь изредка подпевала. Ребята много репетировали, и Мадонна с головой погрузилась в творческий процесс. Она часами терзала гитару, подбирая аккорды к песням. Музыка вдохновляла ее, она чувствовала, что именно здесь в полной мере может выразить свою индивидуальность. Подруга Мадонны по танцшколе Энджи Смит поступила к ним басисткой. Группа дала несколько концертов, но альянса не получилось, отчасти потому, что Мадонне не нравилось делить сцену с другой привлекательной девушкой. К тому же Смит больше любила танцевать, и играть в группе ей быстро надоело.
На ее место пришел Майк Монахэн, а когда появился барабанщик Гэри Берке, Мадонна стала солисткой. Однако песни братьев Гилрой и их доморощенная хореография ее не удовлетворяли. Они ссорились, и однажды Дэн вспылил: «У тебя одни амбиции и ноль таланта!» Мадонну это сильно задело. Она ушла от Дэна вместе с Монахэном и Берке. Втроем они основали новый коллектив под названием «Madonna And The Sky», который тоже быстро развалился. Берке очень уставал на основной работе и раздражался, когда нетерпеливая девушка высказывала критические замечания. Вскоре он покинул группу. К счастью, в это время в Нью-Йорк приехал ее старый мичиганский друг Стив Брэй, который искал себе применение. «У нее уже было несколько готовых песен, не хватало барабанщика. Естественно, мы стали работать вместе», — рассказывает Стив. Результатом этого союза явились «The Millionaires» и «Emmy», подражание ранним «Pretenders».
У Брэя и Мадонны снова вспыхнул роман, но вскоре он понял, что быть ее бойфрендом — это тяжкое испытание. «Есть очень открытые и честные люди, а есть такие: „Со временем ты поймешь, что ты не мой парень и что я встречаюсь с дюжиной других". Она скорее второе, — говорит Брэй. — Я научился… не рассчитывать на ее преданность». Конечно, бедный юноша был разочарован, но все же решил остаться с Мадонной и сконцентрироваться на музыке, которую они вместе создавали. Спустя несколько месяцев она заявила, что отныне группа будет называться «Madonna». Брэй возразил, что это звучит слишком по-церковному. «„Так что же, все песни будут только о тебе?" Позднее я понял, что все это действительно было о ней».
Теперь группа называлась ее именем, и тем не менее Мадонна чувствовала себя очень неуверенно. Ей хотелось найти свой стиль, для этого не хватало чего-то важного. Чтобы найти правильную форму выражения для музыки, которую она слышала внутри, был необходим взгляд профессионала, и таким профессионалом оказалась Камилла Барбон.