Després del segle xvii el territori de la vall del Zambeze havia començat a ser colonitzat per portuguesos i els anomenats "indo-portuguesos" (indis convertits a la religió catòlica que van adoptar noms portuguesos) que rebien territoris (prazos) a canvi d'una renda, i podien ser transmesos a la filla gran durant un màxim de tres generacions retornant després les terres a la corona que podia tornar e entregar-les als colons o "prazeiros" si es considerava que hi havia hagut una bona administració; els terrenys s'adquirien por tractats amb els caps locals i de vegades per matrimonis; les hisendes van arribar a esdevenir autèntics petits estats amb els seus exèrcits dels anomenats "chicundas" i el seu sistema de recaptació d'una renda personal en espècie (cobrada als majors de 16 anys) anomenada "mussoco". Els colons comerciaven amb marfil i esclaus (enviats a Cuba principalment) i venien productes fets a l'Índia Portuguesa.
El 1817 es va crear la capitania colonial de Quelimane, que fou suprimida el 1829 i incorporada a la capitania de "Rios de Sena", fins que fou restablerta el 1853. Els establiments del que després fou la província de Tete van patir atacs dels nadius que fugien dels traficants d'esclaus, a partir del 1830, però no hi va haver atacs al que després fou la província de Zambézia.
El districte colonial de Zambèzia fou creat el 1858 per decret reial, amb les capitanies de Quelimane i Rios de Sena (coneguda com a Zambeze) i abraçava tot el territori de la vall del Zambeze. Els "prazos" foren abolits per primer cop el 1832 i com que l'abolició no fou efectiva es va repetir el 1854. El mateix any es va abolir l'esclavatge i els esclaus foren enviats a Mauricio i Reunion legalment com a contractats. L'impost del mussoco fou substituït per l'anomenat palhota, una mena de contribució sobre les terres. El domini portuguès estava gairebé limitat a Quelimane, i a l'interior la principal hisenda era Maganja de Costa; l'estructura dels prazos va servir de base per convertir als chicundas o xicundas en sipaios, utilitzats contra els pobles de la zona.
Després de 1870 el comerç de la zona, pels interessos de les companyies europees, va derivar cap a les oleaginoses, com el midó i l'oli de copra. Les companyies van organitzar grans plantacions. El 1880 els prazos foren declarats extints per tercera vegada. El 1886 el governador Augusto de Castilho, per obtenir finançament per mantenir el control i ampliar el territori, va imposar el pagament del "mussoco" bé en espècie, bé en treball, i amb els que pagaven l'import amb la seva feina van sorgir les més grans plantacions, especialment de canya de sucre. El 1890 el comissari reial Antonio Eanes va decretar una revisió del treball rural (regulat el 1875), la qual establia que el mussoco ja no s'havia de pagar en espècie i el pagament en feina escassament retribuïda va esdevenir general; el decret obligava també a l'ocupació efectiva de les terres dels prazeiros, i com que aquests les explotaven molt limitadament, van haver de vendre els terrenys o sub arrendar-los, amb el que es van acabar els grans dominis.
El districte de Zambèzia va emetre els seus propis segells a partir del 28 de juliol de 1893 i van estar en ús fins vers el 1920. El 1899 una columna de sipaios de Boror dirigits per George Stucky de Quay, va sotmetre al cap indígena Comgone, assegurant el control dels districtes de Lugela, Mocuba i Namacurra. El 1913, de les prop de nou milions d'hectàrees da Zambèzia, 5,4 milions eren administrades pels arrendataris, i la resta de 3,6 milions estaven reservades per l'estat; no obstant l'àrea realment ocupada per les grans plantacions només era el 0,5% de les terres arrendades; això era degut al fet que els cultius com el cotó i la canya de sucre reclamaven molta mà d'obra, i les companyies no volien invertir en maquinària, ja que sobrava gent i els salaris eren molt baixos i encara es reservava una part de la terra per cultivar aliments pels treballadors evitant així les companyies el cost d'aquests aliments. Una font addicional d'ingressos, en alguns casos, era l'enviament de "contractats" a les plantacions de Sao Tomé (uns 30000 enviats entre 1910 i 1915) i a les mines de Sud-àfrica. D'altra banda l'explotació i les males condicions afavoriren l'emigració d'una part de la població local cap a Transvaal, Swazilàndia i altres llocs.
El 1921 tots els grans prazos (23) havien passat a mans de companyies europees excepte tres. Els prazos eren:
Prazos no dominats per les companyies, tots propers a Quelimane:
Carungo, arrendat a Francisco Gavicho de Lacerda (1906)
Pepino, arrendat a Vitorino Romão da Nazareth
Quelimane Sul, arrendat a Vitorino Romão da Nazareth
Companhia da Zambézia (1892):
Massingire (adquirit el 1897);
Andone (adquirit el 1987);
Anquaze (adquirit el 1897);
Timbué (adquirit el 1900);
Companhia do Boror (1898):
Boror (adquirit el 1898);
Macuse (adquirit el 1898);
Licungo (adquirit el 1898);
Nameduro (adquirit el 1899);
Tirre (adquisició en data desconeguda);
Société du Madal (1904):
Madal (adquirit el 1903 per l'antecessora Gonzaga, Bovay e Ca);
Tangalane (adquirit el 1903);
Cheringone (adquirit el 1903);
Maindo (adquirit el 1904);
Inhassunge (adquirit el 1916);
Empresa Agricola do Lugela (1906):
Lugela (adquirit el 1906);
Milange (adquirit el 1906);
Lomué (adquirit el 1910);
Sena Sugar Estates (1920):
Maganja d'Aquém Chire (adquirit el 1894, per la predecessora, Companhia do Açúcar de Moçambique);
Luabo (1911, per l'antecessora Sena Sugar Factory)
Marral (1911, per l'antecessora Sena Sugar Factory).
segell de Zambèzia, precedent de Zambézia
El 1908 es va crear la circumscripció de Maganja da Costa i el 1918 es van formar dos noves circumscripcions, Alto Molucué i Ile. El 1919 es van formar les de Moebaze (reanomenada Pebane el 1926) i Ossiua (suprimida el 1923 i repartida entre Alto Molocué i Pebane). El 1913 es va dividir en els districtes de Tete i Quelimane que van emetre els seus propis segells de correus. El 1915 Quelimane fou reanomenat Zambézia, però va recuperar el nom de Quelimane posteriorment.
El 1951 Moçambic va esdevenir província portuguesa d'ultramar. El 1963 el districte de Quelimane ja apareix amb el nom de Zambézia i es va convertir en província pel decret llei 6/75 del 18 de gener, efectiu realment amb la independència el 25 de juny de 1975.
Governadors
La província és dirigida per un governador provincial nomenat pel President de la República.
