Vascular phantoms are crucial tools for clinical training and for calibration and validation of medical imaging systems. With current methods, it can be challenging to replicate anatomically-realistic vasculature. Here, we present a novel method that enables the fabrication of complex vascular phantoms. Poly(vinyl alcohol) (PVA) in two forms was used to create wall-less vessels and the surrounding tissue mimicking material (TMM). For the latter, PVA cryogel (PVA-c) was used as the TMM, which was made from a solution of PVA (10% by weight), distilled water, and glass spheres for ultrasonic scattering (0.5% by weight). PVA-c is not water soluble, and after a freeze-thaw cycle it is mechanically robust. To form the wall-less vessels, vessel structures were 3D printed in water-soluble PVA and submerged in the aqueous solution of PVA-c. Once the PVA-c had solidified, the 3D printed PVA vessel structures were dissolved in water. Three phantoms were created, as initial demonstrations of the capabilities of this method: a straight vessel, a stenosed (narrowed), and a bifurcated (branched) vessel. Ultrasound images of the phantoms had realistic appearances. We conclude that this method is promising for creating wall-less, anatomically realistic, vascular phantoms.