The Murchison Widefield Array (MWA) has observed the entire southern sky (Declination, $delta <$ 30 deg) at low radio-frequencies, over the range 72-231 MHz. These observations constitute the GaLactic and Extragalactic All-sky MWA (GLEAM) Survey, and we use the extragalactic catalogue (Galactic latitude, $|b| >$ 10 deg) to define the GLEAM 4-Jy (G4Jy) Sample. This is a complete sample of the brightest radio-sources ($S_{mathrm{151MHz}} >$ 4 Jy), the majority of which are active galactic nuclei with powerful radio-jets. Crucially, low-frequency observations allow the selection of such sources in an orientation-independent way (i.e. minimising the bias caused by Doppler boosting, inherent in high-frequency surveys). We then use higher-resolution radio images, and information at other wavelengths, to morphologically classify the brightest components in GLEAM. We also conduct cross-checks against the literature, and perform internal matching, in order to improve sample completeness (which is estimated to be $>$ 95.5%). This results in a catalogue of 1,863 sources, making the G4Jy Sample over 10 times larger than that of the revised Third Cambridge Catalogue of Radio Sources (3CRR; $S_{mathrm{178MHz}} >$ 10.9 Jy). Of these G4Jy sources, 78 are resolved by the MWA (Phase-I) synthesised beam ($sim$2 arcmin at 200 MHz), and we label 67% of the sample as single, 26% as double, 4% as triple, and 3% as having complex morphology at $sim$1 GHz (45-arcsec resolution). Alongside this, our value-added catalogue provides mid-infrared source associations (subject to 6-arcsec resolution at 3.4 micron) for the radio emission, as identified through visual inspection and thorough checks against the literature. As such, the G4Jy Sample can be used as a reliable training set for cross-identification via machine-learning algorithms. [Abstract abridged for arXiv submission.]