Brains must represent the outside world in a way that allows animals to survive and thrive. In early sensory systems, the way neurons respond to stimuli can be summarized in their receptive fields (RFs), and these are structured to detect certain features. Experimental data show that they are also noisy, but this randomness remains unaccounted for in existing models. By taking this unexplained variability into account, we reveal how the interplay between structure and random noise provides important computational benefits for sensory encoding. Furthermore, structured randomness offers a biological principle that may prove important for machine learning, improving the efficiency of artificial neural networks while offering insight into their function. In particular, we describe biological receptive fields as random, variable samples from parameterized distributions. We make a significant theoretical connection between the foundational concepts of receptive fields in neuroscience and random features in artificial neural networks. We highlight the strength of our approach by successfully applying it to RF datasets from two disparate sensory systems, mechanosensory neurons on insect wings and V1 cortical neurons from mice and monkeys. A key benefit of our approach is that it allows us to model RFs of an entire population of neurons using a handful of parameters. We show theoretical results that structured random receptive fields allow neurons to use well-known mathematical transformations to remove high-frequency components from their inputs and boost signals. Empirical results on classification tasks show that such transformations indeed help learning. When artificial neural networks are initialized with biologically structured randomness, we find that they are more accurate using fewer training examples, smaller network sizes, and fewer gradient steps compared to traditional, unstructured initializations. This structured random model of RFs provides a unifying, mathematically tractable framework to understand sensory encodings across both spatial and temporal domains.