The structures of free-standing zirconium nanowires 0.6-2.8nm in diameter are systematically studied by using genetic algorithm simulations with a tight-binding many-body potential. Several multishell growth sequences with cylindrical structures are obtained. These multishell structures are composed of coaxial atomic shells with the three- and four-strand helical, centered pentagonal and hexagonal, and parallel double-chaincore curved surface epitaxy. Under the same growth sequence, the numbers of atomic strands in inner and outer shells show even-odd coupling and usually differ by 5. The size and structure dependence of angular correlation functions and vibrational properties of zirconium nanowires are also discussed.