Los primeros indicios de asentamiento humano se remontan al 500 a.C. en el área donde actualmente se encuentra el Zandpoortvest y la Douaneplein y existen vestigios de la existencia de un poblado gálico-romano en la zona del actual Korenmarkt. La primera constancia escrita de la ciudad es del año 870, en que Malinas aparece en el inventario de terrenos pertenecientes al reino franco oriental.

La cristianización de Malinas se lleva a cabo en el siglo VII u VIII por San Rumoldo, un monje venido de Irlanda y martirizado en Malinas, en cuyo honor se construye una abadía, probablemente en el mismo lugar en que posteriormente se erigió una catedral, también en su honor. Las paredes de la catedral describen con una serie de imágenes su vida legendaria y milagros.

No se conoce con certeza en qué momento fue creado el Señorío de Malinas, pero sí que a finales del siglo X pertenece a los príncipes-obispos de Lieja. Tras la formación del ducado de Brabante, Malinas permanece siendo un enclave de Lieja; los enfrentamientos entre Lieja y Brabante se traducen en la concesión de gran número de privilegios que contribuyen a la prosperidad de la ciudad.

En 1333, Malinas es vendida al conde Luis I de Flandes, estando desde entonces el señorío de Malinas ligado a los títulos del Conde de Flandes.