Tradiční šajenská společnost byla matrilokální, matrilineární a exogamní. Muž si hledal manželku v jiné šajenské podskupině a po uzavření sňatku se do této podskupiny přestěhoval. Ženy zůstávaly se svými příbuzními v táboře, z něhož pocházely. Děti, které se šajenskému páru narodily, patřily k matčině podskupině. Ve výjimečných případech, kdy matka nežila se svou rodnou skupinou, se původ dítěte odvozoval od skupiny, v níž matka v době porodu pobývala. Určení původu bylo velice důležité při hledání budoucího partnera. I sňatek mezi dosti vzdálenými pokrevními příbuznými se u Šajenů považoval za incest. Totéž platilo, pokud si Šajen vzal Šajenku z vlastní skupiny. Mezi šajenskými tradicionalisty to platí dodnes.

       Jedinou výjimkou z pravidla exogamie byli dlouho Sutajové. Nepočetní Sutajové bývali ještě na přelomu 17. a 18. století samostatnou skupinou, která se podle názoru etnoarcheologa K. H. Schlesiera (1994) v 16. století odštěpila od Arapahů a Atsinů. Později se zapojili do šajenského táborového kruhu a postupně se asimilovali.

       Tradiční matrilokálně-matrilineární model narušil ve 40. až 60. letech 19. století válečnický spolek psích mužů (hotametaneo’o). Vytvořil vlastní sídelní skupinu, kde roli náčelníků převzali vůdcové spolku. Muži ze spolku nežili rozptýleni ve skupinách svých manželek, ale manželky si přiváděli s sebou. V období střetů s armádou Spojených států se toto uspořádání osvědčilo. Skupina byla bojeschopnější a mohla lépe koordinovat své akce. Existenci tohoto sídelního uspořádání víceméně ukončil útok majora Carra na tábor psích mužů u Summit Springs v létě 1869.

       U Šajenů bývalo běžné mnohoženství. Dalšími manželkami se většinou stávaly sestry a sestřenice první ženy. V polygynních rodinách žilo v polovině 19. století asi 40 procent Šajenů. Více manželek mívali především významní muži, náčelníci, vůdcové válečnických společností apod. Systém spolumanželek, které byly zároveň sestrami nebo sestřenicemi, přinášel na planinách nesporné výhody. Mezi ženami existoval dlouholetý přátelský vztah a dokázaly si efektivně rozdělit péči o děti a práci. Díky tomu se polygynní rodiny mohly v 1. polovině 19. století úspěšně zapojit do obchodu s bizoními kůžemi a především jižní Šajeni z něj velmi těžili.

       Předpokládá se, že v 1. polovině 18. století žili předkové dnešních Šajenů ve dvou velkých stálých vesnicích. První skupina se označovala Ȯhmésėhese a udržovala několik svébytných tradic. Objevují se např. zmínky o duhovém týpí, na jehož tyčích visel štít s orlím perem. Symbolika duhy se později stala součástí šajenského slunečního tance. Druhá, početnější skupina si říkala Tsétsėhéstȧhese a opatrovala čtyři posvátné šípy. Poté, co na konci 18. století přešly ke kočovnému způsobu života ve stepích, se obě skupiny (teď již pod společným názvem Tsétsėhéstȧhese) spojily se Sutaji a některými smíšenými, lakotsko-šajenskými skupinami.

       Výrazem jednoty se každé léto stal společný kruhový tábor. Konaly se v něm nejvýznamnější obřady a táboření ukončil společný lov bizonů. Každá skupina (manaho) zaujímala v táborovém kruhu tradicí určené místo. Původní Tsétsėhéstȧhese a tlupy od nich odtržené tábořili na jižní straně; Sutajové tábořili na západě, místě určeném hostům, a Ȯhmésėhese spolu s tlupami, které se od nich odtrhly, tábořili na severní straně. Nejčestnější místa vedle vstupu do táborového kruhu (otevíral se k východu) zaujímalo jádro původních Tsétsėhéstȧhese a Ȯhmésėhese. Kdykoli se oddělila nová skupina, zařadila se vedle Sutajů.

       Rozdělení Šajenů na severní a jižní větev po roce 1830 nebylo náhodné, ale vycházelo z historického dělení na Tsétsėhéstȧhese a Ȯhmésėhese. Větší část Sutajů se připojila k severním Šajenům, ostatní k jižním. Povědomí o tradičních podskupinách přetrvává a při každoročním obřadu slunečního tance každá z rezervačních komunit přesně ví, kde se utábořit.