Вот тут-то Хелависа и решила позвонить Дену с предложением воссоздать группу на основании равенства, братства и честного дележа вымогаемых на входе в клуб денежных средств, но уже без Руслана и под другим названием, которое еще предстояло придумать. Ну и позвонила, ясен пень! Ден выслушал, согласился, что идея неплоха и взял на себя роль главного администратора, а также обзвон всех остальных бывших участников «Тиля» с предложением присоединиться к воссоздаваемому проекту. Состав был обзвонен и полностью согласился с предложением.
И настало 15 октября 1999 года, и появилась группа «Мельница».
Название чуть позже придумала Хелависа объяснив это примерно так: «Очень милое сказочное сооружение, нам подходит». Это потом уже объяснение обросло всякими подробностями того, что подразумевается под словами «милое сказочное сооружение», а именно — «обиталище красноглазого мельника-колдуна из славяно-балтийского фольклора; некий демиургический механизм, не только превращающий зерно в муку, но и творящий свой необыкновенный мир, как мельница Сампо» и т. п. А тогда это была просто очень милая сказочная «Мельница».
Первый концерт состоялся в клубе «Форпост» 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 г.)