In 2390, under the command of Captain Alonzo Vandermeer, the ibn Majid encountered a small ship of unknown design deep in the Vayt sector. Vandermeer informed Starfleet Command of a first contact situation and invited Ambassador Beautiful Flower and his protégé Jana aboard. A few hours later, Vandermeer received a black flag directive from Commodore Oh at Starfleet Security ordering him to kill them, or else the ibn Majid would be destroyed with all hands. Vandermeer carried out the order, and then committed suicide after being confronted by his executive officer Cristóbal Rios. (PIC: "Broken Pieces")
Starfleet subsequently classified the incident and erased the existence of the ibn Majid from official records. As such, in 2399, Rios did not expect retired Admiral Jean-Luc Picard to have heard of it. (PIC: "The End is the Beginning", "Broken Pieces")
This starship was presumably named for the 15th century explorer Ahmad ibn Majid.