Nová Ves byla založena jakýmsi lokátorem Petrem na pozemcích pražského biskupství (na tzv. emfyteutickém právu) za Tobiáše z Bechyně ve druhé polovině 13. století. První písemná zmínka pochází z listiny datované 1287, podle které prodal Matouš z Kouřimi svůj podíl v obci pražskému biskupství. V roce 1342 propůjčil král Jan Lucemburský platy a práva na Novou Ves Hronovi z Masojed a v roce 1397 zde vysadil arcibiskup Olbram ze Škvorce německé právo a svobodnou rychtu. V roce 1418 arcibiskup Konrád z Vechty prodal Novou Ves Albertovi Warentrappea a od této doby se v jejím držení vystřídalo několik majitelů: po roce 1420 Pražané, roku 1437 Jiří z Poděbrad a po něm jeho syn, kníže Jindřich I. Starší z Poděbrad a Minsterberka, který Novou Ves v roce 1481 vyměnil s Českým Brodem za Semice. V jeho držení zůstala ves až do konfiskace roku 1623, kdy připadla knížeti Karlu z Lichtenštejna, který ji připojil k panství Plaňany, s nímž přešla v letech 1716 – 1848 pod správu panství Kostelec nad Černými lesy.
V revolučním roce 1848 byl Janem Klinderou z Nové Vsi čp. 4 svolán tábor lidu na nedaleký vrch Klepec. Na tomto shromáždění proti utlačování českého národa vystoupil František Augustin Brauner, který se významně zasloužil na přípravě zákona o zrušení roboty. Rezoluce z tábora lidu byla předána vládě. Jan Klindera roku 1848 poskytl na sýpce svého statku v Nové Vsi útočiště prchajícímu páteru Václavu Krolmusovi, který odsloužil uprostřed barikád na Václavském náměstí v Praze památnou mši u sochy sv. Václava.
V roce 1850 získala obec samostatnost, ale v roce 1960 byla připojena k Rostoklatům.
Název obce je odvozen od nového založení, latinsky Nova vila, česky přeloženo Nowá wes. Později se používal i německý zápis názvu obce jako Neudorf. V roce 1921 byl kodifikován současný název Nová Ves, po reorganizaci státní správy a začlenění do okresu Kolín byla do názvu doplněna římská číslovka II na odlišení od Nové Vsi I západně od Kolína a Nové Vsi III jižně od Svojšic.
Nová Ves II je administrativní součástí obce Rostoklaty, jejich vlastní katastrální území činí 3,77 km².
Nová Ves II leží na Štolmířském potoce, 2,5 kilometru západně od Českého Brodu (27,5 kilometru severozápadně od Kolína) v nadmořské výšce 254 metry.