For the first time, a stochastic deep convective parameterization to represent variability arising from small-scale processes that are unresolved by traditional deterministic moist convective parameterizations is tested in a general circulation model. Two physical pathways of representing small-scale variability as a stochastic process are explored. First, the relationship between cloud-base mass flux Mb and large-scale convective available potential energy (CAPE) is posited to have a stochastic component (the CAPE-Mb scheme). Second, the vertical structure of heating is modified by a simple random process about the structure given by the traditional convective scheme (the VSH scheme). The CAPE-Mb scheme increases the overall variance of precipitation toward observations with a realistic spatial pattern. The VSH scheme has smaller impacts on precipitation variance but yields preferential enhancement at large spatial scales and low frequencies.