Searching for violations of the no-hair theorem (NHT) is a powerful way to test gravity, and more generally fundamental physics, particularly with regards to the existence of additional scalar fields. The first observation of a black hole (BH) shadow by the Event Horizon Telescope (EHT) has opened a new direct window onto tests of gravity in the strong-field regime, including probes of violations of the NHT. We consider two scenarios described by the Einstein-Maxwell equations of General Relativity and electromagnetism, to which we add a scalar field. In the first case we consider a minimally-coupled scalar field with a potential, whereas in the second case the field is conformally-coupled to curvature. In both scenarios we construct charged BH solutions, which are found to carry primary scalar hair. We then compute the shadows cast by these two BHs as a function of their electric charge and scalar hair parameter. Comparing these shadows to the shadow of M87* recently imaged by the EHT collaboration, we set constraints on the amount of scalar hair carried by these two BHs. The conformally-coupled case admits a regime for the hair parameter, compatible with EHT constraints, describing a so-called mutated Reissner-Nordström BH: this solution was recently found to effectively mimic a wormhole. Our work provides novel constraints on fundamental physics, and in particular on violations of the no-hair theorem and the existence of additional scalar fields, from the shadow of M87*.