We search for ultraluminous Quasi-Stellar Objects (QSOs) at high redshift using photometry from the SkyMapper Southern Survey Data Release 3 (DR3), in combination with 2MASS, VHS DR6, VIKING DR5, AllWISE, and CatWISE_2020_, as well as parallaxes and proper motions from Gaia DR2 and eDR3. We report 142 newly discovered Southern QSOs at 3.8 < z < 5.5, of which 126 have M_145_ < -27 AB mag and are found in a search area of 14486 deg^2^. This Southern sample, utilizing the Gaia astrometry to offset wider photometric colour criteria, achieves unprecedented completeness for an ultraluminous QSO search at high redshift. In combination with already known QSOs, we construct a sample that is >80 per cent complete for M_145_ < -27.33 AB mag at z = 4.7 and for M_145_ < -27.73 AB mag at z = 5.4. We derive the bright end of the QSO luminosity function at rest frame 145 nm for z = 4.7-5.4 and measure its slope to be {beta} = -3.60 +/- 0.37 and {beta} = -3.38 +/- 0.32 for two different estimates of the faint-end QSO density adopted from the literature. We also present the first z ~ 5 QSO luminosity function at rest frame 300 nm.