Группа была основана Билли Хаурделом — гитарным техником, работавшим с Nine Inch Nails, The Smashing Pumpkins, Fishbone, Guns N’ Roses и Tool. Мэйнард Джеймс Кинан, вокалист Tool, услышав демозаписи Билли, сказал что, если тот создаст группу, то он готов стать их вокалистом. Хаурдел после некоторых сомнений согласился, несмотря на то, что сначала хотел чтобы в группе был женский вокал. Также к ним присоединились басистка и скрипачка Пэз Леншантин, гитарист Трой Ван Левен, прежде игравший в Failure, и барабанщик Тим Александр из Primus.
После серии репетиций и выступлений на разогреве у других команд, APC начинают записывать студийный альбом Mer de Noms. Тим Александр вскоре был заменён Джошем Фризом из The Vandals, однако в песне «The Hollow» все ещё можно услышать игру Тима. После завершения альбома, группа принимает участие в нескольких турах в США и Канаде.
К записи второго альбома A Perfect Circle готовились уже без двух музыкантов: Пэз Леншантин и Троя ван Льюена. Пэз присоединилась к группе Zwan, а Трой — к Queens of the Stone Age. Однако Леншантин к тому времени записала почти все партии для бас-гитары для нового альбома. На место покинувших группу музыкантов были приняты Джорди Уайт басист Marilyn Manson, (также известный как Твигги Рамирес, который временно не участвовал в команде Marilyn Manson в период с 2003 по 2007 включительно, участвуя в таких проектах как APC, Nine inch nails и Goon Moon), и гитарист Дэнни Лонер. Однако, Лонер не подошёл группе как второй гитарист, и на новом альбоме его можно услышать только в песне «The Noose». Место Дэнни Лонера занял Джеймс Иха из The Smashing Pumpkins.
Записав второй альбом Thirteenth Step 16 сентября 2003, группа провела остаток года в турах по Северной Америке, Европе и Японии. В 2004 APC продолжили туры по Австралии, Японии, Новой Зеландии и Европе, завершив тур весной выступлениями в США.
Третий альбом eMOTIVe был записан 2 ноября 2004 (день выборов в США) и содержит каверы на антивоенные песни таких музыкантов, как Джон Леннон и Джони Митчелл. 16 ноября 2004, выпустила DVD/CD-комплект названный «aMotion». На нём представлены ранее не издававшиеся видеоклипы, а также би-сайды и ремиксы. Режиссёром клипа к песне «Judith» (2000) был Дэвид Финчер.
Некоторое время будущее A Perfect Circle оставалось неясным. В интервью французскому журналу «Rock Hard» Кинан говорил, что считает APC завершённым проектом и в обозримом будущем изменений не предвидится. Билли Хаурдел подтверждал, что не планирует записи нового альбома или концертных туров.
На официальном сайте A Perfect Circle 19 сентября 2006 можно увидеть запись: «Спящий должен пробудиться! Привет! Извините, некоторое время от нас не было вестей. Были заняты. Билли погружён в работу над сольным проектом, а я гастролирую с TOOL, работаю над сайтом www.puscifer.com и ещё ко всему прочему делаю вино. Не могу сказать когда Билли закончит записывать новый материал, но я слышал многообещающие прогнозы. Я забыл опубликовать тексты песен с 13th step и eMotive, я этим скоро займусь. Так что заходите почаще. Пока. mjk»
9 декабря 2008 Кинан заявил, что он и Билли Хаурдел пишут новый материал для A Perfect Circle, и что в их планы пока что не входит продолжение полноценного турне и даже запись альбома. Вместо этого они сосредоточат внимание на паре композиций, которые скорее всего будут выпущены через интернет.
7 апреля 2009 группа выпускает свой первый релиз после перерыва — мини-альбом Deep Cuts, состоявший из трёх концертных записей и одной демокомпозиции материала Mer de Noms; а 17 сентября Кинан заявил о том, что новый материал уже на подходе.
27 октября 2010 группа дает концерт на шоу Джимми Киммела на канале ЭйБиСи, а в ноябре проводит тур по территории США.
29 июня 2011 года на концерте в Портленде (Орегон) исполнена новая композиция «By & Down».
В октябре 2012 года Кинан в ответ на вопросы по поводу нового материала, заявил следующее: «Мы сбили кое-что, но пока ничего не готово и нет смысла представлять новый материал. Сейчас Хаурдел занят с Ashes Divide, а я — с Puscifer».
2 октября 2012 года на своей странице в Твиттере барабанщик Джош Фриз, объявил об уходе из группы, заявив следующее: «После 13 лет я решил оставить A Perfect Circle без планов на возвращение. Прошу прощения у тех, кто интересовался будущими шоу».
После перерыва в четырнадцать лет A Perfect Circle в 2017-м году анонсировали студийный альбом. Пластинка получила название Eat the Elephant и вышла 20 апреля 2018 года на лейбле BMG. Гитарное звучание группы сменилось более клавишным, более зависимым от текстур и слоёв.
