Exploiting invariances in the inputs is crucial for constructing efficient representations and accurate predictions in neural circuits. In neuroscience, translation invariance is at the heart of models of the visual system, while convolutional neural networks designed to exploit translation invariance triggered the first wave of deep learning successes. While the hallmarks of convolutions, namely localised receptive fields that tile the input space, can be implemented with fully-connected neural networks, learning convolutions directly from inputs in a fully-connected network has so far proven elusive. Whether convolutions can be learnt from scratch has thus been a central problem in neuroscience and machine learning since the seminal work by Olshausen and Field (1996) on unsupervised learning. Here, we show how initially fully-connected neural networks solving a discrimination task can learn a convolutional structure directly from their inputs, resulting in localised, space-tiling receptive fields. By carefully designing data models for the visual scene, we show that this phenomenon relies on the non-Gaussian, higher-order local structure of the inputs, which has long been recognized as the hallmark of natural images. We provide an analytical and numerical characterisation of receptive field formation, which results in an unexpected link with tensor decomposition of higher-order input correlations. The receptive fields learnt by the fully-connected networks match the filters found by training a convolutional network on the same task. These results provide a new perspective on the development of low-level feature detectors in various sensory modalities, and pave the way for the study of higher-level invariances in cortical processing.