Первый концерт состоялся в клубе «Форпост» 29 октября. Причем, в афише все еще значился «Тиль Уленшпигель», поэтому Хелависа начала концерт словами: «Здравствуйте. Вас немножко обманули. Дело в том, что заявлена была группа Тиль Уленшпигель, а сейчас вы видите перед собой группу Мельница, потому что все ушли из группы Тиль Уленшпигель и образовали другую группу. Если кто-то хочет, то он может получить свои деньги обратно, а для тех, кто останется сыграем.» Не помню, чтобы кто-то ушел. И, естественно, тоже остался. Концерт получился дивным, хотя Хелависе было трудновато одновременно играть на гитаре и петь, но эту проблему еще предстояло решить.

И вскоре она была решена. В группу пригласили старого друга Александра Степанова по прозвищу «Грендель», который почитался в их кругах за самого крутого гитариста. Однако же, имея нулевой опыт игры в коллективе (это совсем не то же самое, что играть одному, без ансамбля то есть), Грендель коллектив быстро разочаровал, и тогда родилась «светлая» идея пригласить в группу Алексея. Можно признать, что его опыт игры в коллективе на тот момент также стремился к нулю, а следовательно группа «Мельница» вобщем-то поменяла шило на мыло. Но, тем не менее, в составе задержался надолго, постепенно совершенствовал свои навыки и в итоге даже перестал вызывать игрой гримасы боли на лицах товарищей по группе. Гренделю же еще предстояло Второе Пришествие, которое состоялось в 2001 году, когда Хелависа на полгода покидала группу, уехав в Ирландию на стажировку. Второе Пришествие Гренделя прошло куда удачнее первого.

Стоит добавить, что вначале группа использовала багаж песен «Тиля Уленшпигеля», поэтому и в дебютный альбом «Мельницы» вошли несколько песен, аранжировщиком которых был Руслан Комляков, лидер «Тиля Уленшпигеля», и сейчас трудно точно установить, какие из песен «Тиля» исполнялись на гастрольных концертах уже «Мельницей», а какие приписываются прежнему составу но с новым названием ошибочно…

Да и стоит ли, дело прошлое, и подлинный прорыв в мейнстрим группа совершила уже с полностью своим репертуаром в 2005 году благодаря «Нашему радио» и хит-параду «Чартова дюжина». Поклонники «Мельницы» организовали флешмоб и вывели песню «Ночная кобыла» в лидеры хит-парада. С тех пор «Мельница» — постоянный участник плей-листа «Нашего радио», их песни часто побеждают в хит-парадах.

В том же 2005 году в составе Мельницы произошли изменения, говоря проще — раскол. Несколько участников отделились и образовали группу «Сильфы». Тогда же появилась вторая вокалистка, Алевтина Леонтьева, которая приняла участие в записи альбома «Зов крови» (2006). Алевтина покинула группу в 2007 году.

В 2009 году «Мельница» записала новый альбом «Дикие травы». В этом же году вышел сборник хитов «Мельница: Лучшие песни».

Параллельно с работой в «Мельнице», Хелависа выступает сольно, долгое время распространялись любительские записи её концертов. Первый «официальный» сольный альбом, «Леопард в городе», вышел в 2009 году.

В 2011 году у группы вышел сингл «Рождественские песни», куда вошли две новые песни — «Береги себя» и «Овечка».

28 апреля 2012 года состоялся релиз пятой пластинки «Ангелофрения». В тот же день «Мельница» презентовала новый альбом в Москве, в клубе Arena Moscow. Также вышли DVD-запись концерта-презентации «Диких трав» и бокс-сет «Знак четырёх» — переиздание первых четырёх альбомов группы. В качестве бонуса в «Знак четырёх» вошли песни «Береги себя» и «Овечка», включённые в рождественский сингл 2011 года.

В ноябре состоялись съёмки первого клипа группы и материала для второго клипа с концерта группы в Ижевске 25 ноября 2012 года.

11 января 2013 года вышел рождественский мини-альбом «Радость моя», включающий 5 песен.

26 сентября 2014 года вышел первый официальный концертный альбом группы «Мельница» «Ангелофрения Live», включающий в себя запись 16 песен с презентации альбома «Ангелофрения» в клубе Arena Moscow 28 апреля 2012 года.

Наталья О’Шей (Хелависа) — вокал, ирландская арфа, перкуссия, акустическая гитара, стихи, музыка, аранжировки.

Алексей Орлов (с декабря 2005 года) — электровиолончель, виолончель, мандолина, аранжировки.

Алексей Кожанов (с декабря 2005 года) — бас-гитара, акустическая гитара, аранжировки.

Дмитрий Фролов (с декабря 2005 года) — ударная установка, аранжировки.

Сергей Вишняков (с февраля 2010 года) — акустическая гитара, электрогитара, бэк-вокал.

Дмитрий Каргин (с июня 2013 года) — флейта

Василиса Введенская — альт скрипичный. Лидер фолк-рок-группы «Вилы». Сессионный участник, май 2000.

Сергей Седых — гитара, электрогитара. Лидер рок-группы «Северо-Восток», сессионный участник концертов 2009–2010, принял участие в записи альбома «Дикие травы» (2009).

Ирина Сурина — вокал. Кантри-фолк-певица, бывшая участница группы «Кукуруза» (1991–2000). Приняла участие в записи альбома «Дикие травы».

Елена Никитаева — вокал. Приняла участие в записи альбома «Дикие Травы» и его презентации в СК «Олимпийский» (2009 г.)

Сергей Клевенский — духовые. Принял участие в записи альбома «Дикие травы».

Макс Йорик — электроскрипка. Принял участие в записи альбома «Дикие травы» и его презентациях в СК «Олимпийский» (Москва) и ДС «Юбилейный» (СПб).

Пётр Никулин — диджериду. Принял участие в записи альбома «Дикие травы».

Николай Ооржак — горловое пение. Принял участие в записи альбома «Дикие травы».

Оскар Чунтонов — орган Хаммонда. Клавишник группы Петра Налича, Татьяны Зыкиной. Принял участие в записи альбома «Дикие травы». Сессионный участник московских концертов группы с 2010 г.

Алексей Сапков (Чус) — с октября 1999 года по март 2010 года: гитара, вокал, перкуссия, музыка, стихи, аранжировки. С марта 2010 года: директор и продюсер коллектива.

Алексей Зиновьев — звукорежиссёр сцены.

Иван Савин — художник по свету.

Алексей Денисов — звукорежиссёр (с ноября 2011 года).

Дэн Скурида — гитара, перкуссия, вокал. С основания группы до июля 2002 года. Участник группы «Ветер Воды».

Мария Скурида — скрипка, бэк-вокал. С основания группы до июля 2002 года. Участница группы «Ветер Воды».

Наталья Филатова — флейта. С основания группы до октября 2005 года. Участница группы «Сильфы».

Александр Степанов (Грендель) — гитара, перкуссия, вокал, музыка, аранжировки. С образования «Мельницы» в октябре 1999 года по декабрь 1999 года был участником группы. С новыми силами вернулся в январе 2001 года, чтобы усилить и разнообразить звучание коллектива. В июне 2007 года вновь покинул группу, являлся участником фолк-группы «АнарримА» до её распада.

Дина Хацко — второй вокал, 1999 год.

Александра Никитина — виолончель, 1999 год.

Алексей Даниленко — виолончель, 2000 год.

Ольга Лопина — второй вокал, ноябрь-декабрь 2000 года.

Дина Нигматуллина — виолончель. С 2000 до декабря 2003 года.

Наталья Масевнина — скрипка. С сентября 2002 до сентября 2003 года.

Роман Лютославский (Прощенко) — перкуссия, ударная установка. С сентября 2002 до июля 2004 года.

Инесса Клубочкина (Бурлакова) — скрипка. С октября 2003 до октября 2005 года. Участница группы «Сильфы».

Наталья Котлова — виолончель. С декабря 2003 до октября 2005 года. Бывшая участница группы «Сильфы».

Евгений Чесалов — бас-гитара. С апреля 2004 до октября 2005 года. Участник группы «Сильфы».

Александр Леер — ударная установка, перкуссия. С июля 2004 до октября 2005 года. Бывший участник группы «Сильфы».

Мария Цодокова (Шанти) — вокал, бэк-вокал. В ноябре 2004 года выступала с группой в качестве второй вокалистки.

Ирина Ширяева — вокал, бэк-вокал. В январе-мае 2005 года выступала с группой в качестве второй вокалистки.