In this paper, we describe the development of paraffin surfaces for culture-based detection of mycobacteria in environmental samples. The surfaces use the well-described paraffinophilic nature of mycobacteria to rapidly and selectively differentiate them from non-target microorganisms. New methods of depositing and patterning paraffin were developed, including using butanol or a heat gun to generate molten paraffin that was subsequently deposited by spin coating and patterned by wet and dry etching techniques. Using these techniques, 18 mm glass wafers with paraffin films of 10-70 µm were fabricated and subsequently etched to form different patterns. Prototype paraffin surfaces were experimentally tested to demonstrate the concept of rapid and selective detection of mycobacteria in environmental samples collected from a municipal sewage treatment plant. Our successful demonstration of the culture-based detection on paraffin substrates presents an alternative approach for tracking microorganisms in complex environmental samples.