LOFAR is the only radio telescope that is presently capable of high-sensitivity, high-resolution (<1 mJy/b and <15) observations at ultra-low frequencies (<100 MHz). To utilise these capabilities, the LOFAR Surveys Key Science Project is undertaking a large survey to cover the entire northern sky with Low Band Antenna (LBA) observations. The LOFAR LBA Sky Survey (LoLSS) aims to cover the entire northern sky with 3170 pointings in the frequency range 42-66 MHz, at a resolution of 15 arcsec and at a sensitivity of 1 mJy/b. Here we outline the survey strategy, the observational status, the current calibration techniques, and briefly describe several scientific motivations. We also describe the preliminary public data release. The preliminary images were produced using a fully automated pipeline that aims to correct all direction-independent effects in the data. Whilst the direction-dependent effects, such as those from the ionosphere, are not yet corrected, the images presented in this work are still 10 times more sensitive than previous surveys available at these low frequencies. The preliminary data release covers 740 sqdeg around the HETDEX spring field region at a resolution of 47 with a median noise level of 5 mJy/b. The images and the catalogue with 25,247 sources are publicly released. We demonstrate that the system is capable of reaching an rms noise of 1 mJy/b and the resolution of 15 once direction-dependent effects are corrected for. LoLSS will provide the ultra-low-frequency information for hundreds of thousands of radio sources, providing critical spectral information and producing a unique dataset that can be used for a wide range of science topics such as: the search for high redshift galaxies and quasars, the study of the magnetosphere of exoplanets, and the detection of the oldest populations of cosmic-rays in galaxies, clusters of galaxies, and from AGN activity.