It is shown that non-commutative spaces, which are quotients of associative algebras by ideals generated by non-linear relations of a particular type, admit extremely simple formulae for deformed or star products. Explicit construction of these star products is carried out. Quantum gauge theories are formulated on these spaces, and the Seiberg-Witten map is worked out in detail.