The first record of the village dates back to 1399. At the end of the 14th century Velenice belonged to nearby Zákupy. In 1479 the farmstead was acquired by the Berka brothers of Dubá and Lipá and thus the Velenice estate was permanently connected to the Sloup estate. Therefore later owners of Velenice were holders of the Sloup estate - the Salhausen, Kolowrat and Kinský families.