Группа была сформирована в Москве в 2003 году Дмитрием Аблазовым (также играл SHIT, Коррозия металла, Sinful) и Никитой Nekis Костюченко (также The Vauge (ныне Maskott), Demons of Guilliotine, Anal Cunt). Вскоре к группе присоединяется вокалист по прозвищу Митяй. Придумывая первые песни, Nekis не слышал грайндкора вообще, особенности стиля ему поведал Митяй, охарактеризовав его как «панковский Cannibal Corpse». Скопировано с Dark-World.ru.

Первые концерты группа начала давать в 2004 году, где вместо барабанов и баса включался музыкальный диск с минусами, а гитара и вокал шли вживую. В 2004 году, назвав свой стиль «живой рэп», группа попыталась отыграть на r'n'b вечеринке в одном из московских клубов. После первой же композиции, охрана силой вытолкнула музыкантов со сцены, а потом и из клуба. Во время этого короткого шоу, Coyote и Alcotron подожгли гримерку и выкатились на сцену запутанные в камуфляжной сетке.

В 2005 году состав коллектива был сформирован живыми музыкантами, барабанщиком Анатолием Бойченко (также Merlin, Demons of Guilliotine) и басистом Романом Коняевым. Правда, через месяц на место барабанщика пересел Роман Amar Лозинский (игравший также в SHIT, Antisystem, Bully Boys, Anal Cunt, и т. д.).

В 2005 году было выпущено первое демо "You Are A Fat Putridity", группа начала активно гастролировать по стране, параллельно записывая сингл "The Beautiful People".

В 2005 году в Р-клубе во время ночного концерта с Коррозией Металла, в клуб ворвались 30 человек в масках, вооруженные арматурами и слезоточивым газом. После массовой драки нападавшие бежали, но в дальнейшем про Anal Nosorog распустились слухи, что они фашисты. Сами участники этот факт всегда отрицали, а тексты группы, которые и так весьма редко встречаются в творчестве не несут никакого политического оттенка. Несмотря на это, было отменено много концертов и фестивалей (Obscene Extreme, Moscow Death Fest и т. д.)

В 2007 году был выпущен первый альбом, ставший эталоном русского, да и не только грайндкора - "Condom Of Hate". Диск был выпущен на 4 лэйблах из разных точек мира (Xtreem music - spain, Coyote records - Russia, и т.д…) в разных изданиях, включая юбилейный Digipack с 16-страничным буклетом. Банда стала гастролировать намного чаще, также расширила свою географию, ездили как по России и СНГ, так и по странам ЕС (Финляндия, Швеция, Норвегия, Дания, Эстония, Латвия, Литва и т. д.).

С 2007 года Некис и Амар отыграли 4 тура с Сэтом Путнэмом (Anal Cunt) в качестве музыкантов AxCx. В связи с проблемами в отношениях, состав часто менялся, за короткий период в группе были Дима Койот (Coyote records), Сергей Гевший (EST), Алексей Фетисов (Tintal), Дмитрий Гинкул (Коррозия металла), Сергей Гордеев (Flashbomb). В 2009 году при случайной встрече с Антти Оинноненом (Torsofuck, Arch Goat и куча других банд), который был тур менеджером многих европейских поездок, Антти примкнул к группе в качестве басиста.

В 2009 году в составе происходят изменения - появляется вокалистка Drama Queen. Выходит альбом "Gazavat" с ее участием.