A novel stochastic fluid model is proposed with non-ideal structure factor consistent with compressibility, and adjustable transport coefficients. This Stochastic Hard Sphere Dynamics (SHSD) algorithm is a modification of the Direct Simulation Monte Carlo (DSMC) algorithm and has several computational advantages over event-driven hard-sphere molecular dynamics. Surprisingly, SHSD results in an equation of state and pair correlation function identical to that of a deterministic Hamiltonian system of penetrable spheres interacting with linear core pair potentials. The fluctuating hydrodynamic behavior of the SHSD fluid is verified for the Brownian motion of a nano-particle suspended in a compressible solvent.