Группа основана в 1999 году бывшими участниками группы «Тиль Уленшпигель», которая к тому времени распалась. На афишах первого концерта «Мельницы», состоявшегося 29 октября 1999 года, всё ещё значилось «Тиль Уленшпигель», за что Хелависа извинилась перед публикой. В дебютный альбом «Мельницы» под названием «Дорога сна» вошли несколько песен, аранжировщиком которых был Руслан Комляков, лидер «Тиля Уленшпигеля».
Популярной группа стала в 2005 году благодаря «Нашему радио» и хит-параду «Чартова дюжина». Поклонники «Мельницы» организовали флешмоб и вывели песню «Ночная кобыла» в лидеры хит-парада. С тех пор «Мельница» — постоянный участник плей-листа «Нашего радио», их песни часто побеждают в хит-парадах. В том же 2005 году в составе Мельницы произошли изменения. Большинство участников отделилось и образовало группу «Сильфы». Но в декабре пришли четыре новых участника, двое из которых играли также в группе NetSlov. Тогда же появилась вторая вокалистка, Алевтина Леонтьева, которая приняла участие в записи альбома «Зов крови» (2006). Алевтина покинула группу в 2007 году.
В 2009 году «Мельница» записала новый альбом «Дикие травы». В этом же году вышел сборник хитов «Мельница: Лучшие песни». Параллельно с работой в «Мельнице», Хелависа выступает сольно, долгое время распространялись любительские записи её концертов. Первый «официальный» сольный альбом, «Леопард в городе», вышел в 2009 году. В 2011 году у группы вышел сингл «Рождественские песни», куда вошли две новые песни — «Береги себя» и «Овечка». Сингл издавался ограниченным тиражом для посетителей рождественских концертов группы.
28 апреля 2012 года состоялся релиз пятой пластинки «Ангелофрения». В тот же день «Мельница» презентовала новый альбом в Москве, в клубе Arena Moscow. Также вышли DVD-запись концерта-презентации «Диких трав» и бокс-сет «Знак четырёх» — переиздание первых четырёх альбомов группы. В качестве бонуса в «Знак четырёх» вошли песни «Береги себя» и «Овечка», включённые в рождественский сингл 2011 года. В ноябре состоялись съёмки первого клипа группы[6] и материала для второго клипа с концерта группы в Ижевске 25 ноября 2012 года[7].
11 января 2013 года вышел рождественский мини-альбом «Радость моя», включающий 5 песен. 26 сентября 2014 года вышел первый официальный концертный альбом группы «Мельница» «Ангелофрения Live», включающий в себя запись 16 песен с презентации альбома «Ангелофрения» в клубе Arena Moscow 28 апреля 2012 года. 25 октября 2014 года состоялся юбилейный концерт в Москве, посвящённый пятнадцатилетию группы, а также рождению дочери у виолончелиста Алексея Орлова.
9 октября 2015 года вышел альбом «Алхимия». 3 сентября 2016 года, в день рождения Хелависы, публике был представлен клип на песню «Прощай» с последнего альбома. 15 октября 2016 года состоялся выход нового альбома «Химера», концептуально связанного с предыдущим. В 2017 году переизданы два первых альбома группы, «Дорога сна» и «Перевал». Новое издание включает в себя буклеты с текстами песен и новыми иллюстрациями. 22 сентября 2019 года состоялся релиз юбилейного сборника группы «2.0 (Vintage Sessions)», вышедшего как на CD, так и на виниловой пластинке[8].
Сергей Седых — гитара, электрогитара. Лидер рок-группы «Северо-Восток», сессионный участник концертов 2009—2010, принял участие в записи альбома «Дикие травы» (2009).
Ирина Сурина — вокал. Кантри-фолк-певица, бывшая участница группы «Кукуруза» (1991—2000). Приняла участие в записи альбома «Дикие травы».
Елена Никитаева — вокал. Приняла участие в записи альбома «Дикие Травы» и его презентации в СК «Олимпийский» (2009 г.)
Сергей Клевенский — духовые. Принял участие в записи альбома «Дикие травы».
Макс Йорик — электроскрипка. Принял участие в записи альбома «Дикие травы» и его презентациях в СК «Олимпийский» (Москва) и ДС «Юбилейный» (СПб).
Пётр Никулин — диджериду. Принял участие в записи альбома «Дикие травы».
Николай Ооржак — горловое пение. Принял участие в записи альбома «Дикие травы».
Оскар Чунтонов — орган Хаммонда. Клавишник группы Петра Налича, Татьяны Зыкиной. Принял участие в записи альбома «Дикие травы». Сессионный участник московских концертов группы с 2010 г.
Наталья Филатова — флейта. С основания группы до октября 2005 года. Участница группы «Сильфы».
Александр Степанов (Грендель) — гитара, перкуссия, вокал, музыка, аранжировки. С образования «Мельницы» в октябре 1999 года по декабрь 1999 года и с января 2001 года по июнь 2007 года. Позже в фолк-группе «АнарримА».