Vanadium or V-based solid solution type alloys with a BCC crystal structure are known to absorb the high capacity of protium but not to desorb completely. This paper tried to find new compositional V-based high density protium storage alloys, with the starting composition of V2.5M1 (M=Al, Co, Fe, Mn, Ni, Ti, Zr). It was found that the best composition among studied alloys is V3.5(Zr1/3Ti1/3Ni1/3) where the alloys consist of the BCC phase with the C14 type Laves phase along the grain boundary. The V3.5(Zr1/3Ti1/3Ni1/3) heat-treated alloys have about 2.0 mass% protium storage capacity of the 3rd cycle and have the flat plateau region in the PCT curves. The V70Zr1Ti12Cr17 alloys show higher protium capacity of nearly 2.5 mass% protium as well as flat plateau region. In the present investigations, it was found that the Zr substitution was very effective for easier activation, better plateau region and higher protium capacity, by forming the C14 Laves phase as minor phases in the BCC major matrix phase for various V-based alloys such as V-Ti-Ni (Cr) alloys.