We study the stability of a compressible magnetic plane Couette flow and show that compressibility profoundly alters the stability properties if the magnetic field has a component perpendicular to the direction of flow. The necessary condition of an instability can be satisfied in a wide variety of flows in laboratory and astrophysical conditions. The instability can operate even in a very strong magnetic field which entirely suppresses other magnetohydrodynamics (MHD) instabilities. The growth time of this instability can be rather short and reach approximately 10 shear time scales.