La aerolínea fue fundada el 24 de mayo de 1958 como Martinair Chárter (MAC), por Martin Schröder y John Block, con un avión, un de Havilland Dove y cinco empleados. En 1963, Schröder vendió el 49 % de la compañía a cuatro accionistas de compañías navieras (12,25 % cada uno, que luego se combinaron en Nedlloyd ). KLM más tarde adquiririó el 50 % de las acciones que Martín Schröder conservaba dejándolo fuera de la compañía. El nombre fue cambiado a Martinair Holland en 1966. Se produjo un aumento en el volumen de negocios en 1967, con el ingreso en el mercado de Estados Unidos. Martinair adquirió su primer jet a propulsión año 1971.

En 1991, el primer avión con el "Martinair Cargo" nombre fue introducido, y "Holland" fue eliminado de todas las aeronaves. En 1996, Martinair compró una participación del 40 % en un portador de carga de Colombia Tampa Cargo, con sede en Medellín, que se incrementó a 58 % en 2003. La participación en Tampa fue vendida en febrero de 2008 a Avianca, una empresa colombiana.

El presidente y CEO de Martinair, Martin Schröder, quien recibió el premio Tony Jannus en 1995 por sus contribuciones a la aviación comercial, se retiró en 1998 de las actividades del día a día. ^[2]​

También ese año, la Comisión Europea en Bruselas, rechazó la oferta de KLM para la compra de acciones de Nedlloyd, que habría hecho a KLM el único propietario. En junio de 2007, Martinair anunció que quería un único accionista, de preferencia KLM, y en 2008 se obtuvo el permiso de la Comisión Europea. La transferencia de las acciones restantes tuvieron lugar el 31 de diciembre de 2008.^[3]​

En noviembre de 2007, Martinair cesó sus operaciones de corto alcance para concentrarse en sus actividades de carga y vuelos intercontinentales. Por una reestructuración interna en la empresa, se anuncia que la aerolínea dejaría de operar vuelos comerciales de pasajeros desde noviembre de 2011 y cede su operación a KLM, pasando a ser una aerolínea exclusiva de carga.^[4]​ En noviembre de 2010, la Comisión Europea multó a Martinair en € 29,5 millones, después de una investigación sobre la fijación de precios.^[5]​

Martinair cuenta con amplias operaciones en la mayor parte del mundo. Vuela con Boeing 747-400 (conocido como 747-400SFs o 400BCFs) a Oriente Medio, Lejano Oriente y Australia, y McDonnell Douglas MD-11 a destinos en Europa, América y África.

•   Arabia Saudita: (Riad).
•   Argentina: (Buenos Aires).
•   Baréin: (Manama).
•   Brasil: (Campinas).
•   Chile: (Santiago de Chile).
•   Costa Rica: (San José).
•   China: (Shanghái).
•   Colombia: (Bogotá) (Medellín) (Cali).
•   Ecuador: (Quito, Guayaquil).
•   Emiratos Árabes Unidos: (Dubái, Sharjah).
•   Estados Unidos: (Seattle, Miami).
•   Países Bajos: (Ámsterdam-Schiphol).
•   China: (Hong Kong).
•   India: (Delhi, Chennai).
•   Kenia: (Nairobi).
•   Perú: (Lima).
•   Puerto Rico: (San Juan, Aguadilla).
•   Catar: (Doha).
•   Singapur: (Ciudad de Singapur).
•   Sudáfrica: (Johannesburgo).
•   Sudán: (Jartum).
•   Reino Unido: (Londres).
•   Ruanda: (Kigali)
•   Tailandia: (Bangkok).
•   Uruguay: (Montevideo).
•   Uganda: (Entebbe).
•   Venezuela: (Caracas).
•   Zimbabue: (Harare).
•   Guatemala: (Guatemala).
•   México: (Ciudad de México)
•   San Salvador: (El Salvador)

A febrero de 2025, la flota de Martinair se compone de las siguientes aeronaves, con una edad media de 32.8 años:^[6]​^[7]​^[1]​

Martinair opera sus aviones cargueros con aerolíneas que no poseen este servicio:

•   Avianca.
•   British Airways.
•   KLM.
•   Qantas.
•   Singapore Airlines.
•   Varig.
•   Virgin Atlantic Airways.

• Vuelo 138 de Martinair: el 4 de diciembre de 1974 un Douglas DC-8 se estrella contra una montaña en Sri Lanka, muriendo 191 personas.
• Vuelo 495 de Martinair: el 21 de diciembre de 1992 un Douglas DC-10 se estrella al intentar aterrizar en Portugal, muriendo 56 de los 327 pasajeros.