Velenice jsou starou českou osadou s názvem odvozeným od Velena, což byl pastýř. Nejstarší písemná zmínka o Velenicích zní: "Král Václav II. daroval roku 1305 ves Velenice a 12,5 lánu polí v Podmoklech na královském panství Poděbradském v náhradu za odejmuté statky klášteru jeptišek Benediktínek u sv. Jiří na Hradě Pražském". V roce 1305 byly připomínány jako klášterní majetek a roku 1437 je dal zapsat císař Zikmund k poděbradskému panství. Původně rychtářský dvůr byl povýšen roku 1530 na manství. Po třicetiletých válkách se udržovalo dlouho tajné protestantství. Po vydání josefinského patentu byla ve vsi vystavěna roku 1785 tzv. toleranční modlitebna. U ní fara z opukového zdiva z roku 1830. Další zajímavostí je litinový kříž z konce 19. století a několik kamenných barokizujících lidových staveb. Číslování domů ve Velenicích pochází z roku 1770.

V roce 1924 bylo k žádosti místní obce Velenice povoleno ministerstvem vnitra, aby osady Velenice a Novohrady byly sloučeny v jednu osadu zvanou Velenice.