In this article we construct orthonormal bases for bi-variate anisotropic α-modulation spaces. The construction is based on generating a nice anisotropic α-covering and using carefully selected tensor products of univariate brushlet functions with regards to this covering. As an application, we show that n-term nonlinear approximation with the orthonormal bases in certain anisotropic α-modulation spaces can be completely characterized.