Magnetic skyrmions are topologically stable swirling spin textures with particle-like character, and have been intensively studied as a candidate of high-density information bit. While magnetic skyrmions were originally discovered in noncentrosymmetric systems with Dzyaloshinskii-Moriya interaction, recently a nanometric skyrmion lattice has also been reported for centrosymmetric rare-earth compounds, such as Gd2PdSi3 and GdRu2Si2. For the latter systems, a distinct skyrmion formation mechanism mediated by itinerant electrons has been proposed, and the search of a simpler model system allowing for a better understanding of their intricate magnetic phase diagram is highly demanded. Here, we report the discovery of square and rhombic lattices of nanometric skyrmions in a centrosymmetric binary compound EuAl4, by performing small-angle neutron and resonant elastic X-ray scattering experiments. Unlike previously reported centrosymmetric skyrmion-hosting materials, EuAl4 shows multiple-step reorientation of the fundamental magnetic modulation vector as a function of magnetic field, probably reflecting a delicate balance of associated itinerant-electron-mediated interactions. The present results demonstrate that a variety of distinctive skyrmion orders can be derived even in a simple centrosymmetric binary compound, which highlights rare-earth intermetallic systems as a promising platform to realize/control the competition of multiple topological magnetic phases in a single material. Typically, skyrmions appear in magnet systems which are non-centrosymmetric. Here, using neutron and X-ray scattering, Takagi et al show the emergence of a skyrmion phase in the centrosymmetric material EuAl4. This expands the range of materials potential hosting skyrmions.