We propose the existence of ultracompact minihalos as a new type of massive compact halo object (MACHO) and suggest an observational test to discover them. These new MACHOs are a powerful probe into the nature of dark matter and physics in the high energy Universe. Non-Gaussian energy-density fluctuations produced at phase transitions (e.g., QCD) or by features in the inflaton potential can trigger primordial black hole (PBH) formation if their amplitudes are delta > 30%. We show that a PBH accumulates over time a sufficiently massive and compact minihalo to be able to modify or dominate its microlensing magnification light curve. Perturbations of amplitude 0.03% < delta < 30% are too small to form PBHs, but can nonetheless seed the growth of ultracompact minihalos. Thus, the likelihood of ultracompact minihalos as MACHOs is greater than that of PBHs. In addition, depending on their mass, they may be sites of formation of the first PopIII stars. Ultracompact minihalos and PBHs produce a microlensing light curve that can be distinguished from that of a point-like object if high-quality photometric data are taken for a sufficiently long time after the peak of the magnification event. This enables them to be detected below the stellar-lensing background toward both the Magellanic Clouds and the Galactic bulge.