The establishment of the NMIOTC was granted by the NATO Defense Ministers on June 12th 2003. The first staff members were posted to the NMIOTC Project Office on November 2005. The MOU regarding the relationship between NATO (the Strategic Commanders) and the NMIOTC was signed by the Greek Chief of Defense (CHOD), SACT and SACEUR in the margins of the NATO Military Committee during the CHODs Session in Brussels on November 15th 2005. The NMIOTC Operational Concept was endorsed by SACT and SACEUR on July 2006.

On the 18^th of December 2007 the MoU regarding the participation in NMIOTC manning, activities and provision of training was signed between the Hellenic Ministry of National Defense and the initial sponsoring Nations: Bulgaria, Czech Republic, Romania and Turkey.

On the 17^th of March 2008 the Centre acquired Full Operational Capability. The Official inauguration took place on the 14^th of October 2008 at Souda Naval Base, Crete. In the period leading up to these events, and later on, the Centre consolidated and improved internal organization and its education and training products, and at the same time was committed to make itself widely known. Since the summer of 2008, individuals and units from NATO and Partner nations began to come for training at NMIOTC.

In 2009, NMIOTC also participated in the planning and the conduct of MIO related exercises with the involvement of surface units and more than 200 multinational trainees from more than 10 NATO and Non-NATO entities. The same year NMIOTC also provided certain education to the Standing NATO Maritime Groups, SNMG1 and SNMG2, prior to their deployment in Operation Ocean Shield.

In October 2009 NMIOTC conducted a high level seminar on Maritime Interdiction of Weapon of Mass Destruction. The seminar was the first commitment to support the NATO community in promoting and organizing forums for discussions and sharing of knowledge and experience in the area of Maritime Interdiction related issues.

In 2010, the initial team of NMIOTC Sponsoring Nations was further enriched with the joining of Italy and the assignment of the first Italian officer on September 2010 was fact.

In 2012 the Maritime Chemical, Biological, Radiological Nuclear detection, identification and control operation field trial was conducted.

In 7^th November 2013 the Center was awarded the QA unconditional accreditation by ACT and was the first NETF that obtained this certification.

In 2015 both the UK and the US decided to contribute to the NMIOTC efforts, by assigning maritime operations expert officers to the Center, starting from January  and July respectively, on a rotational basis.

In March 2018 NMIOTC Sponsoring Nations community was further enriched with the joining of Poland by the assignment of the first Polish officer.

In October 2018 NMIOTC has fulfilled 10 years of training presence and the achievement of recognition inside NATO Structure is apparent.

On 2^nd December 2018, NMIOTC was recognized as a NAEMT (National Association of Emergency Medical Technicians) authorized Training Center.

On 31^th May 2019 the center was awarded the 2^nd QA unconditional accreditation by ACT, for 6 more years.

In July 2020 NMIOTC Sponsoring Nations community was further enriched with the joining of Germany by the assignment of the first German PO.

In December 2023, the Centre deployed a Mobile Education and Training Team (METT) in Nouakchott, Mauritania, in order to deliver a tailored training package in the context of the NATO Defence Capacity Building (DCB) Initiative for Mauritania. Since 2016, NMIOTC has supported the Alliance in implementing DCB Initiatives for Partner Nations such as Georgia, Jordan & Mauritania.