Podrijetlo šaha nije pouzdano poznato. Najvjerojatnije je da se šah pojavio prije više od 2.000 godina. Prilikom arheoloških iskopavanja u Uzbekistanu nađene su dvije figurice od slonovače koje pripadaju razdoblju vladavine cara Huviške (2. stoljeće). Stručnjaci smatraju da su to šahovske figurice. U 5. stoljeću nastala je u Indiji posebna vrsta vojne igre na drvenoj ploči - „čaturanga“, što znači četverodni. Čaturanga je kao daleki predak današnjeg šaha bila igra koja je odražavala sastav i poredak tadašnje indijske vojske, koju su sačinjavala 4 roda: pješaštvo, konjica, slonovi i borbena kola, a u sredini su se nalazili radža (kralj) i njegov savjetnik mantrin (današnja kraljica ili dama). Kretanje figura određivalo se bacanjem kocke.
Igru su u 6. stoljeću igrali Perzijanci (čatrang), a od njih u 7. stoljeću preuzeli su je Arapi osvajanjem Irana i tijekom naredna dva stoljeća bila je vrlo populara u arapskim zemljama. Održavana su natjecanja između najboljih igrača, proučena su moguća otvaranja (tabije) i sastavljeni su prvi problemi otvaranja (mansube). Kalif Harun er-Rašid je poslao krajem 8. stoljeća francuskom vladaru Karlu Velikom na poklon šah od slonove kosti.
U 9. stoljeću Arapi su je pod imenom „šatrandž“ prenijeli u Španjolsku, Šatrandž predstavlja viši oblik čaturange. Ishod borbe više ne određuje slučaj (bacanje kockice), već logika i snalažljivost igrača. Igra postiže veliku popularnost i širi se po europskim zemljama sve do Islanda. Francuski kralj Luj IX. je 1254. godine izdao poseban nalog koji je zabranjivao igranje šaha. U Europi je šah usavršen uvođenjem rohade i povećanjem djelovanja kraljice i lovca (kod Arapa je kraljica mogla ići samo po jedno polje ukoso, a lovac je mogao skakati ukoso na svako treće polje: premda je teško bilo izvesti mat, postojala su dva načina za pobijediti - usamljivanjem protivničkog kralja i patom, koji se računao kao pobjeda za patiranu stranu). Sa reformom su ukinuta ova dva načina pobjede.
Usavršavanjem od drevne čaturange igra je poprimala današnji oblik. Nastala je u 15. stoljeću u kada se 1497. godine pojavilo prvo tiskano djelo o šahu koje je napisao španjolski šahist Lusena. Njegovo djelo su nastavili u 16. i 17. stoljeću Španjolac Ruy Lopez de Segura i Talijani Giulio Cesare Polerio i Gioachino Greco, sve dok u 18. stoljeću francuski šahovski majstor Louis-Charles Mahé de La Bourdonnais sa svojim djelom "analyse des Échecs" nije postavio temelje suvremenoj šahovskoj teoriji.