Es un diario que comienza a publicarse –excepto los domingos– el dos de diciembre de 1858 con la intención de ser “indiferente” a las “discusiones sin término” de los “escritores políticos” y por el contrario ofrecer “todo lo que pasa en el mundo” (en España y el extranjero), es decir, escueta información, de ahí que aparezca con el subtítulo “boletín de noticias y avisos”, especialmente locales, y ello a través de un formato de “muy reducidas dimensiones” –en 4º–, ya abandonado por la prensa noticiosa de la época, para convertirse en “el periódico más barato de las Baleares”. Si la suscripción mensual de los periódicos de las islas era de diez reales vellón, este diario lo será a tres, y, además, distribuido conjuntamente con el diario barcelonés El Telégrafo, a siete reales. El Correo de Mallorca saldrá en entregas de cuatro páginas, compuestas a una sola columna, de las prensas de la Imprenta de la Viuda de Villalonga, apareciendo indicado como editor responsable Juan García de Paredes, que más tarde será reemplazado por Juan Villalonga. Clasificado por Bover (1862) como liberal “templado”, podría resultar paradójico que el citado El Telégrafo no pueda ser otro, que el aparecido en Barcelona el primero de noviembre, fundado por Fernando Patxot Ferrer (1812 - 1859), en cuyo prospecto había señalado que “su partido es la España; sus amores, Dios, la humanidad, la patria; sus objetos de veneración, las leyes”, principios que hace explícitamente suyos El Correo de Mallorca. Los contenidos de este diario mallorquín se estructurarían en Sección local (con noticias de Palma, Mallorca, Menorca e Ibiza, con indicaciones útiles para la provincia y todas sus poblaciones); Sección oficial (extractos de las disposiciones del Boletín oficial de la provincia y órdenes y anuncios de las autoridades locales); Sección comercial (precios de los productos de consumo y movimiento portuario); Sección religiosa (santoral y culto), Variedades y Anuncios (en la que incluiría programación teatral, avisos particulares y publicidad comercial). El primero de abril de 1859, introduce “mejoras” en su elaboración, aumentando su formato a folio regular y siendo compuestas sus cuatro páginas a dos columnas. A partir del primero de noviembre de ese mismo año, el tamaño aumenta de nuevo a folio mayor y sus páginas serán compuestas ahora a tres columnas, modificando el subtítulo a “diario de noticias y avisos”, al tiempo que suma nuevos colaboradores, que describe como “jóvenes distinguidos, cuyos trabajos literarios darán amenidad” al periódico. Así mismo, al dejar de ser distribuido conjuntamente con el diario barcelonés El Telégrafo, reestructura sus contenidos y los amplía, estableciendo secciones de Noticias de España, de Provincias y del Extranjero, además de una de alcance o Correo de ayer y de Partes telegráficos, y otra Sección doctrinal o editorial, aunque declara su “imparcialidad” e “independencia” de los partidos políticos. Pretende emular tanto al citado El Telégrafo como al Diario de Barcelona. También publica folletines en el faldón de su primera plana, y su suscripción mensual la reduce a seis reales. El diez de octubre de 1862 experimenta nuevas modificaciones. A partir de ahora lleva el subtítulo “diario de intereses materiales, noticias y avisos de las Islas Baleares”. Se publica todos los días por la mañana, sin excepción, aunque los sábados y los lunes ofrecerá “medio número”, y los domingos y los jueves insertará una novela. Sigue siendo el diario más barato de las islas y “ajeno a la política”. El editor responsable es ya Juan Villalonga y su cuarta plana la ocupa completa la sección de Avisos. Tendrá también una sección de Revista de periódicos. En sus últimas entregas adopta un nuevo diseño, para ser compuesto otra vez a dos columnas, con el subtítulo “diario de intereses materiales de las Baleares”. Su último número en la colección de la Biblioteca Nacional de España corresponde al domingo 28 de febrero de 1864, en su sexto año de edición.