Laser-induced breakdown spectroscopy (LIBS) is a promising technique for the readout of immunochemical assays utilizing indirect detection of labels (Tag-LIBS), typically based on nanoparticles. We have previously demonstrated that Tag-LIBS immunoassay employing yttrium-based photon-upconversion nanoparticles (UCNPs) can reach sensitivity similar to commonly used enzyme and fluorescence immunoassays. In this study, we report on further increasing the sensitivity of UCNP-based Tag-LIBS immunoassay by employing magnetic microbeads (MBs) as the solid phase in the determination of cancer biomarker prostate-specific antigen. Due to the possibility of analyte preconcentration, MBs enabled achieving a limit of detection (LOD) of 4.0 pg·mL, representing two orders of magnitude improvement compared with equivalent microtiter plate-based assay (LOD of 460 pg·mL). In addition, utilizing MBs opens up the possibility of an internal standardization of the LIBS readout by employing iron spectral lines, which improves the assay robustness by compensating for LIBS signal fluctuations and bead-bound immunocomplexes lost throughout the washing steps. Finally, the practical applicability of the technique was confirmed by the successful analysis of clinical samples, showing a strong correlation with the standard electrochemiluminescence immunoassay. Overall, MB-based Tag-LIBS was confirmed as a promising immunoassay approach, combining fast readout, multiplexing possibilities, and high sensitivity approaching upconversion luminescence scanning while avoiding the requirement of luminescence properties of labels.