Перед началом сезона 1999/2000 команда обменяла Твердовского в «Анахайм» и рассталась со старшим тренером Джимом Шонефельдом. Из-за разногласий по новому контракту весь сезон был вынужден пропустить бастовавший Николай Хабибулин. Несмотря на это «Койоты» во главе со своим новым тренером Бобби Фрэнсисом заняли шестое место в Западной конференции.
По ходу сезона 2000/01 у команды появилась новая группа владельцев во главе с Уэйном Гретцки, и после непопадания в плей-офф «Койотис» взяли курс на омоложение состава. Ткачука обменяли в «Сент-Луис», Хабибулина — в «Тампу-Бэй», не был продлён контракт и с Рёником.
В сезоне 2001/02 клуб сенсационно вышел в плей-офф. Основная заслуга в этом принадлежала вратарю Шону Бурку, ставшему по результатам сезона одним из претендентов на звание лучшего игрока НХЛ. Два года спустя команда «скатилась» в число последних и, как следствие, старший тренер Бобби Фрэнсис потерял своё место.
С 2005 по 2009 год тренером клуба был Уэйн Гретцки, но под его руководством «Койоты» ни разу не смогли стать участниками плей-офф Кубка Стэнли.
После ухода Уэйна Гретцки в 2009 году тренером клуба стал Дэйв Типпетт. Под его руководством в сезоне 2009/2010 команда впервые за восемь лет вышла в плей-офф, но в упорной борьбе уступила в первом раунде «Детройт Ред Уингз» со счётом 3–4 в серии.
В сезоне 2010/2011 «Финикс» второй год подряд вышел в плей-офф, но «Детройт Ред Уингз» вновь выбил «койотов» из розыгрыша Кубка Стэнли в первом раунде со счетом 0–4.
После того как в 2009 году клуб обанкротился и стал собственностью НХЛ, многократно сообщалось о возможном переезде франшизы в другой город. В июле 2013 года городской совет Глендейла одобрил сдачу домашней арены «койотов» в долгосрочную аренду фирме «Renaissance Sports and Entertainment». В августе 2013 года НХЛ продала команду группе компаний «IceArizona Acquisition Co LLC». Новые владельцы клуба подтвердили, что команда останется в Глендейле и будет переименована в «Аризону Койотис» с сезона 2014/2015[2]. Перед драфтом 2014 года команда официально сменила название. 12 октября 2014 года Эндрю Бэрроуэй — бизнесмен из Филадельфии, управляющий инвестиционным фондом, приобрёл 51 % акций клуба, став тем самым главным владельцем команды.
10 июня 2015 года городской совет Глендейла проголосовал за досрочное расторжение договора между городом и клубом об аренде арены, на которой выступают «койоты», что поставило под сомнение дальнейшее пребывание команды в городе[3]. В июле того же года, контракт между Глендейлом и «Койотис» был переподписан на новых условиях сроком на 2 года[4].
19 августа 2021 года власти города Глендейл отказались продлевать договор аренды арены с клубом и объявили, что сезон 2021/22 станет последним для «Аризоны» на этой арене. 10 февраля 2022 года руководство клуба объявило о переезде «Койотис» в Темпе с сезона 2022/23, где на время строительства новой арены будет выступать на стадионе Университета штата Аризона вместимостью 4600 зрителей[5].
«Койотис» несколько лет не могли найти место для новой арены, а в мае 2023 года проект нового стадиона «Аризоны» был и вовсе отклонён на референдуме среди жителей города Темпе[6].
18 апреля 2024 года Совет директоров НХЛ одобрил продажу «койотов» самой лиге за $ 1 млрд и создание клуба в Солт-Лейк-Сити за $ 1,2 млрд, который будет принадлежать бизнесмену и владельцу клуба НБА «Юты Джаз» Райану Смиту[7][8]. $ 200 млн. будут выплачены владельцам лиги в качестве платы за переезд. При этом «Юта» не будет считаться правопреемеником «Койотис». Все хоккеисты «Аризоны», тренерский штаб и прочий персонал, а также драфт-пики переходят в новую команду в Юте. Но несмотря на это, лига и прежний владелец «койотов» Алекс Меруэло оставляли за собой права на название «Аризона Койотис», их логотип и весь остальной брендинг. Франшиза переведена во временно неактивный статус сроком на 5 лет. Потенциально «Аризона Койотис» сможет вернуться в лигу и набрать состав через драфт расширения, если до 2029 года будет построена новая арена[9].
В апреле мэр Скоттсдейла выступил против строительства арены для «Койотис» на границе Скоттсдейла и Финикса из-за полного отсутствия подходящей инфраструктуры[10]. В итоге в июне «койотам» вновь отказали в планах на постройку арены. Меруэлло в конце концов отказался от планов о постройке нового стадиона, необходимого для возвращения в НХЛ, передав все права на франшизу самой лиге[11]. В июле 2024 года Алекс Меруэлло официально отказался от планов возвращения команды, и тем самым клуб официально прекратил свое существование.
Сокращения: И = сыгранные матчи в регулярном чемпионате, В = победы, П = поражения, ПО = поражения в овертаймах, О = очки, ЗШ = забитые шайбы, ПШ = пропущенные шайбы, РШ = разница шайб (+-), Рег. чемп. = место, занятое в указанном дивизионе по итогам регулярного чемпионата, Плей-офф = результат в плей-офф