První písemná zmínka o obci pochází z roku 1386, tj. za panování Václava IV. („Barrtoss de Przibissowa“). V té době, dle predikátu, se zde již nalézá tvrz na výšině 229 m.n.m., cca 800 m od vzdálené řeky Cidliny (210 m.n.m.). Tvrz byla umístěna v mírném údolí mezi vrchem VINICE (252 m.n.m) a lesem zvaným VÍNO u zdroje vody – studánky.

Majetek měl řadu pánů, z kterých byl nejvýznamnější rok Pernštejnů a Kinských. Převýšov patřil pod chlumecké panství.

Vojtěch z Pernštejna nechal v prvé polovině 16. století založit na jižních opukových svazích vinice, které nepřetržitě plnily své poslání 120 let, v období (1618-1648) třicetileté války skončilo pěstování vinné révy. Po třicetileté válce, podle údajů Berné ruly (1654), zbylo z Přebejchova 8 vypálených usedlostí a 3 opuštěné domky, vše bez duší.

Na mapě z roku 1740 je vyznačeno přemístění obce o cca 500 m směrem severním pod názvem Nová Ves, Prebejsskow. Podle údajů Tereziánského katastru, který byl uzavřen roku 1757, má Nová Ves, Prebejsskow 10 chalup a 53 duší. V Sommerově topografii z roku 1835 má Přebeyschow, Neudorf  38 domů a 230 obyvatel.

V druhé polovině 19. století pomohla tomuto kraji výstavba železnice z Velkého Oseka do Chlumce nad Cidlinou. V roce 1870 (na katastru obce byla postavena železniční stanice Žiželice) a zprovoznění železniční tratě v roce 1873 mezi Chlumcem n. Cidlinou a Hradcem Králové.

V roce 1880 má obec Převýšov též Nová Ves 65 domů a 452 obyvatel. Po první světové válce, ve které zahynulo 8 mužů – vojáků, má v roce 1921 Převýšov 84 domů a 435 obyvatel. V roce 1950, po 2. světové válce, žilo ve 117 domcích 368 obyvatel.