The M'dok Empire was an interstellar state bordering the United Federation of Planets and ruled by the M'dok.
In the 22nd century, the Empire and the Federation fought a war which the Federation won. As a result of the war, the Federation imposed a tough peace treaty on the M'dok, limiting them to a small territory and only police ships, nothing larger.
In 2364, the Empire suffered a great famine and the M'dok were forced to look for food beyong their borders. This search led them to raid Tenara and carry off Tenarans, presumably to be eaten on the home world. These raids were only stopped when the USS Enterprise-D and USS Centurion intervened and fought the M'dok. (TNG novel: The Captains' Honor)