The frequency of barred spiral galaxies as a function of redshift contains important information on the gravitational influence of stellar disks in their dark matter halos and also may distinguish between contemporary theories for the origin of galactic bulges. In this paper we present a new quantitative method for determining the strength of barred spiral structure, and verify its robustness to redshift-dependent effects. By combining galaxy samples from the Hubble Deep Field North with newly available data from the Hubble Deep Field South, we are able to define a statistical sample of 18 objectively-defined low-inclination barred spiral systems with $I_{814W}<23.2$ mag. Analysing the proportion of barred spiral galaxies seen as a function of redshift, we find a significant decline in the barred fraction beyond redshifts $zsimeq 0.5$. The physical significance of this effect remains unclear, but several possibilities include dynamically hotter (or increasingly dark-matter dominated) high-redshift discs, or an enhanced efficiency in bar destruction at high redshifts. By investigating the formation of the ``orthogonal axis of Hubbles classification tuning fork, our result complements studies of evolution in the early--late sequence, and pushes to later epochs the redshift at which the Hubble classification sequence is observed to be in place.