  Parity binomial edge ideals of simple undirected graphs are introduced.
Unlike binomial edge ideals, they do not have square-free Gr\"obner bases and
are radical if only if the graph is bipartite or the characteristic of the
ground field is not two. The minimal primes are determined and shown to encode
combinatorics of even and odd walks in the graph. A mesoprimary decomposition
is determined and shown to be a primary decomposition in characteristic two.
