Pierwszą pisaną wzmianką o Kuleszkach nazywanych Dużymi jest zapis o nadaniu przez księcia Janusza I Grzymkowi i Pawłowi 10 włók ziemi (blisko 170 hektarów) w widłach rzek Brok Mały i Brok Duży. Ci dwaj szlachetnie urodzeni, zgodnie ze wspomnianym dokumentem pochodzili z Marszewa – obecnie jest to wieś Sokolniki koło Płońska. Działo to się około roku 1420 i tę datę uznaje się jako początek istnienia miejscowości.
Historia miejscowości
Historia Andrzejewa
Andrzejewo znajduje się na terytorium historycznego Mazowsza. Tą częścią Polski rządzili książęta z linii piastowskiej. Po bezpotomnej śmierci Stanisława i Janusza III ich siostra Anna w 1526 r. przekazała księstwo królowi Zygmuntowi Staremu. Od tego czasu Mazowsze dzieliło się na trzy województwa: płockie, rawskie i mazowieckie. Województwo mazowieckie składało się z dziesięciu ziem, m.in. z ziemi nurskiej, na która składały się powiaty: kamieniecki, nurski i ostrowski. Taki podział przetrwał do rozbiorów Polski.