К концу первой недели занятий Мадонна нахально спросила у Ленг, не возьмет ли та ее в свою нью-йоркскую труппу. "Я была ошарашена, — вспоминает Ленг, — и ответила, что надо посмотреть, но, возможно, место найдется. Я спросила, как она намерена добираться до Нью-Йорка. Она сказала: «Не волнуйтесь, доберусь». Потом в заявлениях для прессы Мадонна утверждала, будто «выступала в танцевальной группе Элвина Эйли», но на самом деле она начинала заниматься в третьем составе труппы Американского центра танца. И все же этот опыт оказался волнующим и полезным: Мадонна впервые попала под пристальные взгляды молодых артистов, не менее честолюбивых, чем она сама. «Мне показалось, будто я оказалась на съемках „Славы“, — сказала она в интервью журналу „Роллинг Стоун“, — там были сплошь латинозы и черные, и все рвались в звезды». В Нью-Йорке Мадонне было одиноко; она часто ходила в Центр Линкольна, садилась у фонтана и плакала. «Я вела дневник, — говорит она, — и молилась, чтобы у меня появился хоть один друг… Но мне ни разу не захотелось вернуться домой. Ни разу». Столкнувшись со столь суровой конкуренцией, Мадонна в конце ноября 1978 года оставила занятия у Эйли и перешла в танцевальную школу Перл Лэнг. Требовательный стиль Лэнг предполагал жесткую дисциплину. Как и Марта Грэм, она видела современный танец лаконичным, драматичным, угловатым. Мадонна определяет хореографию Лэнг как «болезненную, мрачную, проникнутую чувством вины. Очень католическую по духу».
В отличие от прочих танцовщиц, занимавшихся в трико, Мадонна носила мешковатую футболку, порванную на спине и скрепленную огромной булавкой. Но эксцентричная манера одеваться не умаляла ее таланта импровизационной танцовщицы. Лэнг вспоминает, что Мадонна была «исключительна. Она была талантлива — такая хрупкая, но взрывная. Многие способны выполнить любые акробатические элементы, но в ней было нечто поэтическое». Благодаря своей худобе Мадонна впервые появилась на сцене в роли голодающего ребенка из гетто в спектакле о Катастрофе «Я никогда больше не видела бабочку». «Она была достаточно тощей, чтобы сойти за еврейского ребенка из гетто, — вспоминает Лэнг. — И танцевала она восхитительно». Но больше всего ей запомнилась поза Мадонны — танцовщицы из другой современной вещи « La Rosa en Flores». «Там был очень эффектный, но сложный мостик. Мадонна сделала его с таким блеском, что у меня перед глазами она до сих пор в этой роли и в этом изгибе».
Лэнг признает, что у Мадонны была «мощь, энергия, чтобы перейти от чисто внешнего эффекта к чему-то более волнующему. В танцоре я первым делом ищу именно эту внутреннюю силу, и в Мадонне она была». Еще у Мадонны была пылкость, привлекавшая Лэнг, — некоторое время. Но вскоре Мадонна стала «гулять» с наиболее темпераментными танцорами труппы и опаздывать на репетиции. Лэнг не могла спокойно выносить столь вопиющий вызов своему авторитету, и вскоре они начали переругиваться на глазах у всей труппы. «Они походили на двух тигриц, которые ходят кругами, примериваясь одна к другой, — вспоминает бывшая танцовщица группы Лэнг. — Перл была очень требовательна ко всем ученикам, но Мадонна не из тех, кто легко подчиняется приказам, особенно если чувствует себя правой». Спорили они ожесточенно, и не раз Мадонна в ярости выбегала из студии. «В конечном итоге, — говорит танцовщица, — она всегда возвращалась и делала так, как требовала Перл. Мадонна хотела совершенствоваться в танце и прекрасно все понимала». Были у Мадонны и другие, не менее насущные проблемы. Она все еще жила на 4-ой Восточной улице, с трудом сводя концы с концами и все больше полагаясь на помощь друзей в том, что касалось еды и средств к существованию. В поисках пищи она, бывало, даже шарила по мусорным бакам. Если ей попадался пакет с эмблемой «Бюргер Кинг» или «МакДональдс», то мясо она, будучи вегетарианкой, выбрасывала, но булочку и жареную картошку съедала. Бывали дни, когда она маковой росинки во рту не держала, но, по словам коллег, это никак не отражалось на ее работе.
Чтобы немного подзаработать, Мадонна подалась в натурщицы и стала позировать обнаженной. Этот промысел она испробовала еще в Мичиганском университете. «Я действительно была в хорошей форме, — вспоминает она, — и мой вес был даже немного ниже нормы, так что мышцы и скелет хорошо прорисовывались. Я была у них одной из лучших натурщиц — меня легко мыло рисовать. Поэтому у меня сложилось что-то вроде постоянного круга». Она выяснила, что может зарабатывать до ста долларов в день, в то время как восемь часов изнурительной работы официанткой приносили всего пятьдесят. Вскоре она стала позировать обнаженной перед группами из трех-четырех человек. «Так я подружилась с этими людьми».