Euclid constructs the square at Proposition 46 of Book I: on a given straight line, to describe a square. The method is a perpendicular and two transfers of length. Raise a perpendicular at one end of the segment, cut it to the segment's own length, then use the compass to fix the fourth vertex from the two ends. The perpendicular itself comes from the vesica construction: two arcs of equal radius about the two endpoints cross at two points, and the line through those crossings is perpendicular to the original.
The square is constructible for the simplest possible reason. Gauss-Wantzel requires a side count of the form: a power of 2 multiplied by a product of distinct Fermat primes. Four is 2 squared, a pure power of two, needing no Fermat prime at all. The same holds for 8, 16, 32 and every further doubling, so bisecting the arcs of a square gives the octagon, then the 16-gon, indefinitely.
Euclid needs the square immediately, because Proposition 47 is the theorem of Pythagoras, stated as an equality between the areas of squares raised on the three sides of a right triangle rather than as an algebraic formula. Book II then proves what are now read as algebraic identities in the form of statements about rectangles and squares.
The square is also the standard instrument for constructing surds. The diagonal of a unit square is sqrt 2. Erect a unit perpendicular at the end of that diagonal and the new hypotenuse is sqrt 3, and repeating the move produces the spiral of Theodorus, which yields the square root of every whole number in turn using nothing but a straightedge and a right angle.