На запад на Великие Равнины шайены мигрировали в результате давления со стороны сиу, которые, в свою очередь, двигались на запад под натиском оджибвеев и кри. В результате строительства в верхней части р. Арканзас в 1832 году торгового поста Форт-Бента огромная часть племени решила переселиться на юг, тогда как остальные продолжали кочевать у истоков рек Северный Платт и Йеллоустон. Так племя разделилось на две части, ставшие известными как Северные и Южные. Переселение на юг положило начало жестокой войне шайенов с кайовами и команчами, закончившейся в 1840 году заключением мира. Самым серьезным сражением этой войны была
Шайены в разные времена воевали с сиу, оджибвеями, кри, ассинибойнами, черноногими, сарси, кроу, гровантрами, ютами, шошонами, банноками, арикарами, хидатсами, манданами, понками, канзами, ото, миссури, омахами, осейджами, пауни, команчами, кайовами, кайова-апачами, потоватоми, сауками и фоксами. И белые, и индейские современники считали шайенов одними из самых яростных и храбрых бойцов. На вопрос, воины какого из враждебных кроу племен были самыми храбрыми, вождь Много Подвигов не задумываясь ответил, что ими были шайены. Капитан Вильям Кларк писал в 1881 году: «Они (шайены –
С 1860 по 1878 год шайены принимали активное участие в войнах с американцами вместе с кайовами и команчами на юге и с сиу на севере. Свой первый договор с США шайены подписали в 1825 году. Изначально отношения племени с белыми людьми были весьма дружественными. Когда в 1839 году несколько человек из партии Пеория были захвачены сиу на Орегонской тропе на р. Южный Платт, 400 шайенов появились в селении сиу и сдерживали молодых воинов, пока белым не удалось спастись. Спустя два года, весной 1841 года, Николас Доусон отъехал от каравана трапперов и мехоторговцев, чтобы поохотиться, и вернулся испуганный, без мула, ружья и пистолета. Белые поставили фургоны в круг в ожидании нападения краснокожих. Вскоре появилась группа шайенов. Они были настроены мирно и сообщили, что разоружили Доусона, дабы тот с испугу не убил кого-нибудь из них. Шайены вернули ему все вещи, добавив по подарку за каждую отобранную вещь.
Бешеный Мул, известный шаман шайенов. 1873 г.
В том же году около пятисот шайенов, сиу и арапахо атаковали селение шошонов, в котором находилась часть охотников Генри Фраеба. Остальные трапперы вместе с Фраебом были на охоте. Трапперы приняли участие в бою на стороне шошонов, в результате чего трое из них были убиты. Чуть позже разъяренные индейцы атаковали возвращавшихся к селению трапперов Фраеба. Основной бой вели шайены и сиу, а арапахо лишь следили за ходом сражения, подбадривая союзников. Индейцы убили еще троих трапперов, в числе которых оказался и сам Генри Фраеб.
Племена были раздражены потерями в схватках с трапперами Фраеба и в следующем году прочесывали территорию к западу от Ред-Бьюте в поисках белых людей. Вблизи Индепенденс-Рок 350 шайенов, оглалов и арапахо окружили отряд Элайджа Уайта, проводником которого был знаменитый Томас Фицпатрик. На переговорах индейцы предупредили Фицпатрика, что эта тропа закрыта и любая группа белых людей, обнаруженная здесь впоследствии, будет уничтожена. Нападения на американцев продолжались, но говорить о начале крупномасштабной войны против американцев еще было рано. 26 августа 1856 года несколько воинов остановили почтовый дилижанс, чтобы попросить немного табака, но возница перепугался настолько, что выхватил револьвер и начал стрелять. В форт Кирни на р. Платт он примчался со стрелой, пробившей руку. Капитан Джордж Стюарт с 41 кавалеристом был отправлен в погоню за «враждебными» шайенами. Двигаясь вниз по реке, он наткнулся на лагерь из 80 шайенов, которые, не чувствуя за собой вины, не ожидали нападения и поздно поняли, что кавалеристы прибыли с намерением атаковать их. Им пришлось бежать. Нападение Стюарта привело к серии набегов на дилижансы и переселенцев.