La provincia cuenta con un total de 11 municipios que han sido parte todos de la antigua provincia de La Habana desde su creación en 1878. El antecedente directo de una organización territorial con el nombre de Mayabeque data de la década de 1960 cuando surgieron las Regiones o Regionales como eslabón intermedio entre los municipios y las provincias. El Regional Mayabeque estuvo conformado por los municipios Melena del Sur, Osvaldo Sánchez y Catalina de Güines (ambos inexistentes como municipios antes de 1959, y actualmente localidades de Güines), San Nicolás, Madruga (sin Aguacate), Nueva Paz y Palos (actualmente localidad de Nueva Paz), con cabecera en Güines.

Por otra parte, el Regional San José comprendía los municipios de San Antonio de las Vegas (después absorbido por el municipio San José), Madruga, Aguacate (actualmente localidad de Madruga), Jaruco, San Antonio de Río Blanco (ahora localidad de Jaruco), Santa Cruz del Norte, Canasí (este territorio formó parte de la provincia de Matanzas, actualmente es localidad del municipio Santa Cruz del Norte y cabecera en San José de las Lajas. También formaron parte del Regional San José los municipios de Cuatro Caminos (tradicionalmente parte de Santa María del Rosario-Cotorro) y Campo Florido que incluía los barrios de Minas y Barreras, tradicionalmente partes de Guanabacoa. Con la División Político Administrativa (DPA) de 1976 que creó la Provincia de Ciudad de La Habana, los poblados de Cuatro Caminos y Campo Florido pasaron a la misma, el primero al municipio Cotorro, y el segundo a Habana del Este, mientras que Minas y Barreras fueron devueltos a Guanabacoa.

La DPA abolió los Regionales y redujo los municipios tomando como cifra crítica 20 000 habitantes, aboliendo incluso los municipios históricos de San Antonio de las Vegas y Aguacate. En la actual provincia de Mayabeque se incluyeron también los municipios occidentales de Batabanó, Quivicán (con La Salud, también municipio histórico eliminado en 1976) y Bejucal, integrantes antes de 1976 del Regional Ariguanabo (con cabecera en San Antonio de los Baños, actual provincia de Artemisa).