Understanding the formation and evolution of the very first stars and galaxies represents one of the most exciting and challenging questions facing the scientific community today. Since the universe was filled with neutral hydrogen at early times, the most promising method for observing the epoch of the first stars is using the prominent 21-cm spectral line of the hydrogen atom (Hogan & Rees 1979, Madau et al. 1997). Current observational efforts (Furlanetto et al. 2006) are focused on the reionization era (cosmic age around 500 million years), with earlier times considered much more challenging. Here we discuss the formation of the first stars in light of a recently noticed effect of relative velocity between the dark matter and gas (Tseliakhovich & Hirata 2010). We produce simulated maps of the first stars and show that the relative velocity effect significantly enhances large-scale clustering and produces a prominent cosmic web on 100 comoving Mpc scales in the 21-cm intensity distribution. This structure makes it much more feasible for radio astronomers to detect early stars from a cosmic age of less than 200 million years. We thus hope to stimulate much more theoretical and observational work focused on a first detection of these early sources.