We present Bistable Auxetic Surface Structures, a novel deployable material system based on optimized bistable auxetic cells. Such a structure can be flat-fabricated from elastic sheet material, then deployed towards a desired double-curved target shape by activating the bistable mechanism of its component cells. A unique feature is that the deployed model is by design in a stable state. This facilitates deployment without the need of complex external supports or boundary constraints. We introduce a computational solution for the inverse design of our Bistable Auxetic Surface Structures. Our algorithm first precomputes a library of bistable auxetic cells to cover a range of in-plane expansion / contraction ratios, while maximizing the bistability and stiffness of the cell to ensure robust deployment. We then use metric distortion analysis of the target surface to compute the planar fabrication state as a composition of cells that best matches the desired deployment deformation. As each cell expands or contracts during deployment, metric frustration forces the surface towards its target equilibrium state. We validate our method with several physical prototypes.