Abstract: Spiral arms are one of the most important features used to classify the morphology of local galaxies. The cosmic epoch when spiral arms first appeared contains essential clues to their formation mechanisms as well as the overall galaxy evolution. In this letter, we used James Webb Space Telescope (JWST) images from the Cosmic Evolution Early Release Science Survey to visually identify spiral galaxies with redshift $0.5\leq z\leq4$ and stellar mass $\geq10^{10}\; M_\odot$. Out of 873 galaxies, 216 were found to have a spiral structure. The spiral galaxies in our sample have higher star formation rates (SFRs) and larger sizes than non-spiral galaxies. We found the observed spiral fraction decreases from 48% to 8% at $z\sim0.75-2.75$. These fractions are higher than the fractions observed with the Hubble Space Telescope (HST). We even detect possible spiral-like features at redshifts $z>3$. We artificially redshifted low redshift galaxies to high redshifts and re-inspected them to evaluate observational effects. By varying the input spiral fraction of the redshifted sample, we found that the input fraction of $\sim40$% matches the observed fraction at $z=2-3$ the best. We are able to rule out spiral fractions being $<20$% (3$\sigma$) for real galaxies at $z\sim3$. This fraction is surprisingly high and implies that the formation of spiral arms, as well as disks, was earlier in the universe.