Der Ort wurde schon im Jahre 1088 erstmals urkundlich erwähnt, im Jahre 1277 gab es eine Holzkirche der Benediktiner von Tyniec.[1] Der Name Gaj ist die polnische Bezeichnung für Hain.
In den Jahren 1801 und 1808 verbrachte General Józef Bem[1] die Sommerferien im lokalen Gutshof.
1918, nach dem Ende des Ersten Weltkriegs und dem Zusammenbruch der k.u.k. Monarchie, kam Gaj zu Polen. Unterbrochen wurde dies nur durch die Besetzung Polens durch die Wehrmacht im Zweiten Weltkrieg. Es gehörte dann zum Generalgouvernement.
