The Murchison Widefield Array (MWA) has observed the entire southern sky (Declination, {delta}<30{deg}) at low radio-frequencies, over the range 72-231MHz. 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_151MHz_>4Jy), 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_178MHz_>10.9Jy). Of these G4Jy sources, 78 are resolved by the MWA (Phase-I) synthesised beam (~2' at 200MHz), and we label 67% of the sample as 'single', 26% as 'double', 4% as 'triple', and 3% as having 'complex' morphology at ~1GHz (45" resolution). We characterise the spectral behaviour of these objects in the radio, and find that the median spectral-index is {alpha}=-0.740+/-0.012 between 151MHz and 843MHz, and {alpha}=-0.786+/-0.006 between 151MHz and 1400MHz (assuming a power-law description, S_{nu}_{prop.to}{nu}^{alpha}^), compared to {alpha}=-0.829+/-0.006 within the GLEAM band. Alongside this, our value-added catalogue provides mid-infrared source associations (subject to 6" resolution at 3.4um) 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. We also estimate the angular size of the sources, based on their associated components at ~1GHz, and perform a flux-density comparison for 67 G4Jy sources that overlap with 3CRR. Analysis of multi-wavelength data, and spectral curvature between 72MHz and 20GHz, will be presented in subsequent papers, and details for accessing all G4Jy overlays are provided at https://github.com/svw26/G4Jy.