One of the first stages of planet formation is the growth of small planetesimals and their accumulation into large planetesimals and planetary embryos. This early stage occurs much before the dispersal of most of the gas from the protoplanetary disk. Due to their different aerodynamic properties, planetesimals of different sizes/shapes experience different drag forces from the gas at these stage. Such differential forces produce a wind-shearing effect between close by, different size planetesimals. For any two planetesimals, a wind-shearing radius can be considered, at which the differential acceleration due to the wind becomes greater than the mutual gravitational pull between the planetesimals. We find that the wind-shearing radius could be much smaller than the gravitational shearing radius by the Sun (the Hill radius), i.e. during the gas-phase of the disk wind-shearing could play a more important role than tidal perturbations by the Sun. Here we study the wind-shearing radii for planetesimal pairs of different sizes and compare it with gravitational shearing (drag force vs. gravitational tidal forces). We then discuss the role of wind-shearing for the stability and survival of binary planetesimals, and provide stability criteria for binary planetesimals embedded in a gaseous disk.