Prince Valdemar was born on 27 October 1858 at Bernstorff Palace in Gentofte north of Copenhagen. His father was Prince Christian of Denmark, later King Christian IX. His mother was Princess Louise of Hesse-Kassel. He was baptised on 21 December 1858.
In March 1863, the Danish royal family, including four-year-old Valdemar, travelled to London for the wedding of his eldest sister, Alexandra, to the Prince of Wales, the son and heir of Queen Victoria. That November, his parents succeeded to the throne of Denmark following the death of King Frederick VII.
Prince Valdemar received his early education from tutors. In the summer of 1874, he accompanied his father during his visit to Iceland for the millennium celebrations. After his confirmation in 1874, as was customary for princes at that time, he started a military education and entered the naval college. In 1879, he was sub-lieutenant and in 1880 lieutenant. In the following years, he participated in several naval expeditions. From 1883, Valdemar lived at Bernstorff Palace near Copenhagen with his nephew Prince George of Greece, who had been taken as a boy to Denmark to be enlisted in the Danish royal navy, and be consigned to the care of Valdemar, who was an admiral in the Danish fleet. Feeling abandoned by his father on this occasion, George would later describe to his fiancée the profound attachment he developed for his uncle from that day forward.