До поселения в резервацию кайовы делились на две части, известные как токинахьюп, или Люди Холода, и геахалего — от команчского кеахади. Эти термины были эквивалентны делению племени на северную и южную части. Первая кочевала вдоль р. Арканзас и границы штата Канзас, а вторая больше времени проводила с команчами в Стейкед-Плейнс. Кроме того, кайовы делились на шесть общин, одну из которых – куато – приблизительно в 1780 году полностью уничтожили сиу. В лагерном круге, начиная от входа, общины располагались в следующем порядке: ката (Отрезанные), когуи (Олень), кайгву, кингеп (Щит), семат (кайова-апачи) и конгтальюи (Черные).
Первый договор с правительством США кайовы заключили в 1837 году. В течение многих лет кайовы и их союзники воевали с мексиканцами и техасцами, но с американцами на севере поддерживали дружеские отношения. Приток переселенцев увеличивался, и 27 июля 1853 года правительство США подписало новый договор с кайовами, команчами и кайова-апачами, по которому племена согласились сохранять мир с американцами, жителями Техаса и мексиканцами, а также позволяли основать на их территории военные форты и дороги. Взамен им причитались ежегодные выплаты товаров на 18 000 долларов в течение десяти лет. В последующие годы отряды кайовов, направлявшиеся против навахов и ютов, периодически совершали грабежи белого населения. В итоге во время раздачи ежегодных товаров индейский агент сказал им, что, если не прекратятся нападения, Великий Белый Отец пришлет войска, дабы наказать их. Верховный вождь Дохасан (Маленькая Гора) ответил: «Белый вождь дурак и трус… На этой земле есть три вождя – белый, испанский и я. Вождь испанцев и я – мужчины. Иногда мы приносим беды друг другу, захватывая лошадей и скальпы, но мы не впадаем в бешенство и не ведем себя подобно глупцам. Но белый вождь – дитя и, как дитя, сразу же начинает злиться. Когда мои молодые воины, чтобы не дать своим женщинам и детям умереть с голоду, забирают немного сахара или кофе у белого человека, проходящего через наши земли, убивая и разгоняя дичь на своем пути, белый вождь злится и обещает прислать солдат. Я давно жду их, но они не приходят. Он трус, и у него женское сердце. Ты передай великому белому вождю мои слова».
В 1860 году войска получили приказ наказать кайовов и команчей, но успеха они не достигли. В марте из фортов Райли, Кобб и Юнион вышли колонны солдат. Одной из них, выступившей из форта Райли, командовал майор Джон Седжвик. Его колонна состояла приблизительно из 500 кавалеристов и группы разведчиков-дел аваров, которыми руководил широко известный на Диком Западе делавар Падающий Лист. Спустя несколько месяцев колонна достигла Нового Форта Бента, ни разу не столкнувшись с индейцами. Вскоре были получены сведения о военном отряде кайовов, и капитан Вильям Стил с отрядом из 89 человек бросился в погоню. Они проскакали 56 миль, но вынуждены были повернуть назад, не встретив ни одного краснокожего. Тем временем кайовов заметили в районе Нового Форта Бента. За ними выслали лейтенанта Стюарта с кавалеристами. Кайовы оказались зажаты между отрядами Стюарта и Стил а. В результате боя вдоль р. Кайова-Крик, штат Колорадо, кайовы ранили трех бледнолицых, а сами, согласно рапорту, потеряли убитыми двух воинов. Кроме того, солдаты захватили 16 женщин и детей и 40 лошадей и мулов. Пленников передали индейскому агенту Вильяму Бенту.
Начавшаяся в следующем году Гражданская война отвлекла правительство США от проблем с враждебными индейцами. Осенью 1863 года стало известно, что сиу, шайены, кайовы, кайова-апачи, команчи и часть арапахов планируют весной начать на Равнинах полномасштабную войну. В июне 1864 года к племенам отправили гонцов с сообщением, что всем дружески настроенным индейцам следует поставить свои лагеря около военных постов, остальные же будут считаться враждебными и подвергнутся уничтожению. Откликнулась только часть арапахов и шайенов. В августе индейский агент сообщал из форта Лайон, что получены приказы убивать всех индейцев, обнаруженных на равнинах. В 1864 году нападения индейцев на Южных равнинах так участились, что все ранчо и станции на территории 400 миль были покинуты. В октябре 1865 года в устье р. Арканзас с кайовами, кайова-апачами, команчами, шайенами и арапахо был подписан новый мирный договор. В 1866 году умер Дохасан, являвшийся верховным вождем кайовов в течение 33 лет. С того времени, по мнению Джеймса Муни, начался упадок племени. Сохраняя мирные отношения с США, кайовы продолжали совершать рейды в Техас, жестокую войну с которым они вели на протяжении всего XIX века.