How big were the first planetesimals? We attempt to answer this question by conducting coagulation simulations in which the planetesimals grow by mutual collisions and form larger bodies and planetary embryos. The size frequency distribution (SFD) of the initial planetesimals is considered a free parameter in these simulations, and we search for the one that produces at the end objects with a SFD that is consistent with asteroid belt constraints. We find that, if the initial planetesimals were small (e.g. km-sized), the final SFD fails to fulfill these constraints. In particular, reproducing the bump observed at diameter D~100km in the current SFD of the asteroids requires that the minimal size of the initial planetesimals was also ~100km. This supports the idea that planetesimals formed big, namely that the size of solids in the proto-planetary disk ``jumped'' from sub-meter scale to multi-kilometer scale, without passing through intermediate values. Moreover, we find evidence that the initial planetesimals had to have sizes ranging from 100 to several 100km, probably even 1,000km, and that their SFD had to have a slope over this interval that was similar to the one characterizing the current asteroids in the same size-range. This result sets a new constraint on planetesimal formation models and opens new perspectives for the investigation of the collisional evolution in the asteroid and Kuiper belts as well as of the accretion of the cores of the giant planets.