Bihermitian complex surfaces are oriented conformal four-manifolds admitting two independent compatible complex structures. Non-anti-self-dual bihermitian structures on ${\mathbb R}^4$ and the four-dimensional torus $T^4$ have recently been discovered by P. Kobak. We show that an oriented compact 4-manifold, admitting a non-anti-self-dual bihermitian structure, is a torus or K3 surface in the strongly bihermitian case (when the two complex structures are independent at each point) or, otherwise, must be obtained from the complex projective plane or a minimal ruled surface of genus less than 2 by blowing up points along some anti-canonical divisor (but the actual existence of bihermitian structures in the latter case is still an open question). The paper includes a general method for constructing non-anti-self-dual bihermitian structures on tori, K3 surfaces and $S^1\times S^3$. Further properties of compact bihermitian surfaces are also investigated.

1991 Mathematics Subject Classification: 53C12, 53C55, 32J15.