Pierwszy zachowany zapis o miejscowości pochodzi z 1284 z dokumentu wystawionego przez kancelarię księcia wielkopolskiego oraz późniejszego króla Polski Przemysła II. Potwierdził on zwolnienia immunitetowe, dodając do nich nowe i zezwalając na lokację wsi na prawie niemieckim dla posiadłości kasztelana poznańskiego Tomisława z Szamotuł herbu Nałęcz, tj. dla dziedzin Szamotuły wraz z przynależnościami, a w tym m. in. z Gajem Małym.
W 1419 odnotowano, że Dobrogost Szamotulski powinien zapłacić (łac. „in villis” tj. prawdopodobnie ze swych wsi) Szczuczyn i Gaj Mały panu Mikołajowi Pyser plebanowi w Szamotułach tytułem zaległych świadczeń na jego rzecz 14 grzywien szer. groszy.
W 1460 bracia Jan oraz Jan Świdwa z Szamotuł na swych połowach miasta Szamotuły oraz wsi Gaj Mały i Jastrowie (obecnie to Jastrowo) dali dożywotnio swej siostrze Beacie tytułem jej części dóbr ojczystych i macierzystych 20 grzywien monety obiegowej czynszu rocznego, 3 małdraty żyta, dwie ćwiertnie (łac. „mensura”) grochu, jedną ćwiertnię prosa, dwa kamienie łoju, 20 wozów drzewa opałowego co kwartał, jednego rybaka do połowu w stawie szamotulskim. W 1499 Wincenty Świdwa z Szamotuł pozwany został o 8 grzywien czynszu rocznego dla kościoła w Kórniku w powiecie pyzdrskim.