První zmínka o vsi pochází z roku 1399, kdy jsou jako první majitelé Velenic zmiňováni Pancířové ze Smojna. Na konci 14. století patřily Velenice k nedalekým Zákupům, jejichž dočasnými majiteli byli též Pancířové. V období husitských válek a války proti lužickým městům toho není o Velenicích příliš známo. Za krále Vladislava II. Jagelonského (1471-1516) bylo velenické panství převedeno ke královskému dvoru a o něco později zrušeno.

V 70. letech 15. století získal Velenice Melichar z Kouče, od něho v roce 1475 koupil vesnici i dvůr Mikuláš z Lutic. V roce 1479 získali statek bratři Berkové z Dubé a Lipé, čímž došlo k trvalému připojení velenického manství k panství sloupskému. Dalšími majiteli Velenic tedy byli držitelé sloupského panství - Salhausenové, Kolowratové, Kokořovci a Kinští.