Context. Fossil groups (FG) are expected to be the final product of galaxy merging within galaxy groups. In simulations, they are predicted to assemble their mass at high redshift. This early formation allows for the innermost M∗ galaxies to merge into a massive central galaxy. Then, they are expected to maintain their fossil status because of the few interactions with the large-scale structure. In this context, the magnitude gap between the two brightest galaxies of the system is considered a good indicator of its dynamical status. As a consequence, the systems with the largest gaps should be dynamically relaxed. Aims: In order to examine the dynamical status of these systems, we systematically analyze, for the first time, the presence of galaxy substructures in a sample of 12 spectroscopically-confirmed fossil systems with redshift z ≤ 0.25. Methods: We apply a number of tests to investigate the substructure in fossil systems in the two-dimensional space of projected positions out to R200. Moreover, for a subsample of five systems with at least 30 spectroscopically-confirmed members we also analyze the substructure in the velocity and in the three-dimensional velocity-position spaces. Additionally, we look for signs of recent mergers in the regions around the central galaxies. Results: We find that an important fraction of fossil systems show substructure. The fraction depends critically on the adopted test, since each test is more sensitive to a particular type of substructure. Conclusions: Our interpretation of the results is that fossil systems are not, in general, as relaxed as expected from simulations. Our sample of 12 spectroscopically-confirmed fossil systems need to be extended to compute an accurate fraction, but our conclusion is that this fraction is similar to the fraction of substructure detected in nonfossil clusters. This result points out that the magnitude gap alone is not a good indicator of the dynamical status of a system. However, the subsample of five FGs for which we were able to use velocities as a probe for substructures is dominated by high-mass FGs. These massive systems could have a different evolution compared to low-mass FGs, since they are expected to form via the merging of a fossil group with another group of galaxies. This merger would lengthen the relaxation time and it could be responsible for the substructure detected in present-time massive FGs. If this is the case, only low-mass FGs are expected to be dynamically old and relaxed. The redshift catalog is only available at the CDS via anonymous ftp to http://cdsarc.u-strasbg.fr (ftp://130.79.128.5) or via http://cdsarc.u-strasbg.fr/viz-bin/qcat?J/A+A/586/A63