Pewnego dnia świat zmienił się na zawsze. Cywilizacja upadła, a jej resztki przetrwały na grzbietach Kolosów, gigantycznych istot przemierzających postapokaliptyczne pustkowia. Ich miasta są jedynymi miejscami, gdzie płynie woda i rosną drzewa, lecz pozostają zamknięte dla ludzi. Wędrujemy więc po ruinach świata jako dzieci Kolosów, szukając nowej przyszłości.
Children of the Colossi to eurogra typu „dudes-on-a-map”, w której gracze wcielają się w plemiona rywalizujące o kontrolę nad jajami Kolosów oraz o możliwość oswojenia nowo narodzonych istot. Rozgrywka toczy się pomiędzy dynamiczną mapą pustkowi a modułowymi planszami Kolosów. Gracze poruszają swoje jednostki, zbierają cenne jaja, wykluwają młode Kolosy i walczą o wpływy w kluczowych regionach. Każde rozmieszczenie jednostek ma znaczenie, a odpowiednie planowanie ruchów i pozycji jest kluczowe dla zwycięstwa.
Gracze mogą wysyłać swoich wysłanników do miast Kolosów, aby zdobywać przewagi i zasoby, lub kierować ich na pustkowia, gdzie rywalizują o jaja składane podczas wędrówek gigantów. Wraz z postępem gry mapa zapełnia się jajami, zwiększając napięcie i tworząc nowe konflikty o pozycję.
W grze nie ma bezpośredniej eliminacji jednostek, zamiast tego kluczowe są taktyczne manewry, kontrola obszarów i wykorzystanie kart, które pozwalają wpływać na rozwój sytuacji.
Każdy z pięciu Kolosów oferuje unikalny zestaw akcji i kart sztandarów, jednak w każdej rozgrywce aktywne są tylko trzy z nich, co zapewnia dużą zmienność strategii.