The discovery of gravitational waves from binary black hole mergers has renewed interest in primordial black holes forming a part of the dark matter density of our Universe. Various tests have been proposed to test this hypothesis. One of the cleanest tests is the lensing of fast radio bursts. In this situation, the presence of a compact object near the line of sight produces two images of the radio burst. If the images are sufficiently separated in time, this technique can constrain the presence of primordial black holes. One can also try to detect the lensed image of the mini-bursts within the main burst. We show that this technique can produce the leading constraints over a wide range in lens masses ≳ 2 M⊙ if the primordial black holes follow a single mass distribution. Even if the primordial black holes have an extended mass distribution, the constraints that can be derived from lensing of fast radio bursts will be the most constraining over wide ranges of the parameter space. We also show that this technique can probe exotic compact boson stars and fermion stars and outline the particle physics parameter space which can be probed.