Quantum field theories on noncommutative Minkowski space are studied in a model-independent setting by treating the noncommutativity as a deformation of quantum field theories on commutative space. Starting from an arbitrary Wightman theory, we consider special vacuum representations of its Weyl-Wigner deformed counterpart. In such representations, the effect of the noncommutativity on the basic structures of Wightman theory, in particular the covariance, locality and regularity properties of the fields, the structure of the Wightman functions, and the commutative limit, is analyzed. Despite the nonlocal structure introduced by the noncommutativity, the deformed quantum fields can still be localized in certain wedge-shaped regions, and may therefore be used to compute noncommutative corrections to two-particle S-matrix elements.