До 1996 клуб выступал в Виннипеге под названием «Виннипег Джетс».
В конце 90-х «Койотис», имея в составе таких хоккеистов, как Ткачук, Джереми Рёник, Теппо Нумминен, Твердовский, Хабибулин показывали неплохую игру в регулярных чемпионатах, но проигрывали в первых раундах розыгрыша Кубка Стэнли. «Анахайм», «Детройт», «Сент-Луис», «Колорадо» по очереди побеждали «Койотов» с 1997 по 2000 год.
Перед началом сезона-99/2000 команда обменяла Твердовского обратно в «Анахайм» и рассталась со старшим тренером Джимом Шонефельдом. Из-за разногласий по новому контракту весь сезон был вынужден пропустить бастовавший Николай Хабибулин. Несмотря на это, «Койоты» во главе со своим новым тренером Бобби Фрэнсисом заняли шестое место в Западной конференции.
По ходу сезона-2000/01 у команды появилась новая группа владельцев во главе с Уэйном Гретцки, и после непопадания в плэй-офф «Койотис» взяли курс на омоложение состава. Кейт Ткачук был обменян в «Сент-Луис», забастовщик Хабибулин — в «Тампу Бэй», не был продлён контракт и с Джереми Рёником.
В сезоне-01/02 клуб сенсационно вышел в плэй-офф. Основная заслуга в этом принадлежала голкиперу Шону Бурку, ставшего по результатам сезона одним из претендентов на звание лучшего игрока НХЛ. Два года спустя команда «скатилась» в число аутсайдеров и, как следствие, старший тренер Бобби Фрэнсис потерял свое место.
После локаута тренером клуба стал Уэйн Гретцки. В первый год его работы, в сезоне-05/06, «Койоты» снова остались за чертой участников плэй-офф. В сезоне 2010-2011 команда дошла до плэй-офф,но уступила Детройту со счетом 0:4 в серии.
