La provincia de Santa Marta, también llamada gobierno de Santa Marta durante la época imperial española, fue una entidad administrativa y territorial de la Nueva Granada, creada el 16 de febrero de 1533 en el Virreinato del Perú a partir de los terrenos orientales de la Provincia de Tierra Firme. En 1717 una Real Cédula expedida por el rey Felipe V de España creó el Virreinato de Nueva Granada, por medio de la cual la provincia fue agregada a este último.
Durante la emancipación de las colonias americanas (1810-1816), Santa Marta permaneció fiel a la Corona española, dimitiendo de las invitaciones de alianza tanto de Santafé como de las Provincias Unidas de la Nueva Granada. En la época de la Gran Colombia hizo parte del Departamento del Magdalena, el cual cubría territorialmente todo lo que hoy es la costa Caribe de Colombia.
Posteriormente a la disolución de este país (1830) perteneció a la República de la Nueva Granada, de carácter centralista, hasta que finalmente se implantó el sistema federal en la Nueva Granada en 1858 y la provincia pasó a ser entonces el Estado Soberano del Magdalena.
Historia Época precolombina miniatura|250px|izquierda|Orfebería Tayrona.
La región estaba dominada por tres grupos indígenas principales: Caribes, Tayronas y Arhuacos, si bien otras etnias importantes como los Malibú y los Chimila también habitaron la zona, hacia el interior. La mayoría de estos grupos fueron exterminados por diversas causas (enfermedades, esclavitud, guerras) una vez los españoles llegaron a tierras americanas. Los que sobrevivieron se refugiaron en la Sierra Nevada de Santa Marta y en la península de la Guajira.
Conquista española
La costa Caribe de la Nueva Granada fue una de las primeras en ser visitadas por los conquistadores españoles. Fue en 1499 que Alonso de Ojeda bordeó las costas de la que luego sería la provincia y gobernación de Santa Marta, que en aquella época era llamada Tierra Firme.
miniatura|250px|Provincias indígenas de la Gobernación de Santa Marta, alrededor de 1500.
Para 1510 se erigieron varias gobernaciones en la costa del Atlántico neogranadino, que iban desde el cabo Gracias a Dios, en el actual Nicaragua, hasta la península de la Guajira, llegando más tarde hasta el delta del río Orinoco, siendo las primeras en crearse: Santa Marta, Cartagena, Nueva Granada y Popayán, que dependían de la Real Audiencia de Santo Domingo. La jefatura de la gobernación estaba en manos de un gobernador. A medida que los exploradores y conquistadores penetraban más en el territorio, se iban ampliando o creando nuevas gobernaciones.
A principios del llegaron a la entonces llamada provincia de la Tierra Firme Vasco Núñez de Balboa y Rodrigo de Bastidas. Después de una larga travesía de exploración por tierra, Balboa fue nombrado jefe de la conquista y pacificación del Darién. Fue en el ejercicio de dicha labor que Balboa descubrió el Mar del Sur, además de obtener un inmenso botín de oro y perlas y hacer algunas fundaciones. Luego envió Balboa a Pedro de Arbolancha a España con los quintos reales del oro y perlas, encomendándole además la misión de comunicar al Rey la noticia del descubrimiento de un nuevo mar, el Mar del Sur, y solicitando la gobernación de Castilla del Oro. En mayo de 1514 llegó Arbolancha a la Corte de Madrid, con la sorpresa de que la noticia se había adelantado, y la Corte ya había nombrado a un gobernador, llamado Pedro Arias Dávila, hermano del marqués de Puñonrostro.
Pedro Arias Dávila, nombrado gobernador de Castilla de Oro, había salido de España el 12 de abril de 1514, es decir, un mes antes de la llegada de Pedro de Arbolancha, el enviado de Balboa, a la Corte de Madrid. Como gobernador recién nombrado, el Rey le proporcionó a Arias Dávila una armada compuesta de quince embarcaciones y mil quinientos hombres, sin contar familias ni tripulaciones. Entre los oficiales reales que hacían parte de la comitiva, se encontraban el cronista Gonzalo Fernández de Oviedo y el obispo franciscano fray Juan de Quevedo, a los cuales el Rey les había encargado dirigir el Consejo del Gobernador.
Luego de hacer escalas en Canarias y Santo Domingo, el gobernador llegó a las costas de lo que habría de ser Santa Marta. Al poner pie en tierra, la comitiva fue atacada por guerreros indígenas que ya antes habían alcanzado una victoria sobre el capitán Colmenares. Sin embargo, las tropas del gobernador tomaron la ventaja y persiguieron a los indígenas hasta un valle escondido en donde los nativos tenían sus casas y sementeras. Las calles del poblado indígena, según el relato de los cronistas, eran tan rectas y bien hechas que parecían trazadas a cordel. Allí permanecieron los españoles varios días, descubriendo enterradas unas urnas de barro en las que los indígenas depositaban las cenizas de sus difuntos. También encontraron mantas de algodón de muy buena hechura, y al interrogar a los indígenas, éstos les dijeron que las mantas provenían del interior, de una región montañosa y muy lejana.
miniatura|250px|Ejecución de Vasco Núñez de Balboa.
Después de algún tiempo, partieron los hombres de Arias Dávila hacia el Darién, llegando a las inmediaciones de Santa Marta la Antigua, que había sido fundada por Diego de Nicuesa, desde donde el gobernador envió mensajeros a Vasco Núñez de Balboa para conminarle a que se sometiera a su autoridad. Balboa, que en ese momento se encontraba construyendo su casa con la ayuda de algunos indígenas, recibió el mensaje con gran sorpresa, pues esperaba que el Rey lo nombrara a él gobernador. Entonces los hombres de Balboa, que eran alrededor de cuatrocientos cincuenta, se sublevaron ante la noticia y conminaron a Balboa a que se opusiese al poder de Arias Dávila. Sin embargo, Balboa tranquilizó a sus hombres y los convenció de que fueran a recibir con honores al gobernador, al que todos le prestaron obediencia. Balboa fue recibido por Espinoza, recién nombrado alcalde mayor, y Arias Dávila le encargó varias misiones con el fin de tenerlo alejado del poder, pues sabía que Balboa no sólo era apreciado entre sus hombres, sino también entre los nativos. El gobernador, incluso, le ofreció a Balboa en matrimonio a una hija suya, que tenía en España. Pasado un tiempo, Arias Dávila no pudo soportar más la buena reputación que tenía Balboa entre la población, y lo hizo arrestar, aduciendo que quería independizarse, y condenándolo a muerte.
Debido a la excesiva crueldad que Arias Dávila mostraba para con los indígenas, el padre Francisco de San Román, desconcertado después de una matanza de nativos ordenada por el gobernador, presentó quejas ante el obispo Juan de Quevedo, quien también estaba al tanto de los malos tratos que Arias Dávila daba a los indígenas. En 1517, el obispo viajó a España para presentar el caso ante la Corte. En España se encontró con fray Bartolomé de las Casas, que también iba en una misión en defensa de los indígenas. El obispo Quevedo fue escuchado en audiencia ante el Emperador Carlos V y su Real Consejo, que expidió órdenes de respetar las disposiciones dictadas por el Consejo de Indias, que ordenaba buenos tratos y evangelización para los nativos. Sin embargo, las disposiciones reales fueron en su mayor parte desatendidas por Arias Dávila.
Como muestra de rechazo por la actitud cada vez más tiránica e intransigente de Arias Dávila, los padres Jerónimos trasladaron la silla episcopal a un nuevo territorio, fundado con el nombre de Panamá en 1518. Allí erigieron catedral y cabildo eclesiástico, y fue allí donde murió el obispo Juan de Quevedo, siendo reemplazado por el dominicano fray Vicente Pedraza.
Fundación de Santa Marta miniatura|250px|Monumento en honor a Rodrigo de Bastidas, fundador de Santa Marta.
En diciembre de 1521, Rodrigo de Bastidas, que tenía sus posesiones en la isla de Santo Domingo, pidió del Emperador Carlos V licencia para la fundación de una ciudad en la costa firme, señalando su jurisdicción desde el Cabo de la Vela hasta las Bocas de Ceniza del río Magdalena. El 6 de noviembre de 1524 se firmó en Madrid la capitulación que dejaba en firme el poblamiento de la provincia, y el 29 de julio de 1525 llegó Bastidas con su comitiva en cuatro buques a una ensenada cerca de Gaira. Por conmemorarse aquel día la festividad de Santa Marta de Betania, le dio a aquel sitio el nombre de Santa Marta, aunque para algunos historiadores, el nombre ya le había sido dado a la bahía desde 1501, cuando fue descubierta, mientras que Bastidas habría llegado en febrero de 1525. Bastidas desembarcó con cerca de cincuenta españoles, algunos de ellos con sus esposas, con el fin de formalizar la colonización. Entre los colonos que llegaron con Bastidas, figuraban Pedro Villafuerte como teniente general, el capitán Rodrigo Álvarez Palomino como maestre de campo, Juan Ledesma como contador real, el portugués Antonio Díaz de Cardoso y el capitán Juan de Sanct Martín, entre otros.
Ante la llegada de los colonos, los nativos de Gaira y Taganga ofrecieron un pacto de paz a los españoles, pero los tayronas y bondas no estuvieron dispuestos a hacer lo mismo y, por el contrario, atacaron el poblado español en múltiples ocasiones con flechas envenenadas. Entre tanto, Bastidas entró en alianza con los gairas, los tagangas y los dorsinos, quienes trabajaron en la fortificación de la ciudad, inicialmente con empalizadas. Poco después, debido a las insalubres condiciones de vida, Bastidas cayó enfermo. Entonces su teniente, Juan de Villafuerte, encabezó una conjura junto con Pedro de Porras y otros siete soldados descontentos por lo que consideraban el excesivo buen trato que Bastidas daba a los indígenas. Un día, aprovechando que Bastidas estaba en cama debido a su enfermedad, entraron a la habitación y lo atacaron con varias puñaladas. Sin embargo, cuando salieron, Bastidas, que no había muerto, comenzó a gritar pidiendo auxilio. Acudió entonces el maestre de campo de Bastidas, Rodrigo Álvarez Palomino, quien con la ayuda del resto de pobladores persiguió a los conjurados, y aunque estuvieron algunos días escondidos entre el monte, fueron capturados y enviados a juicio a Santo Domingo, donde fueron condenados a la horca. Bastidas nombró entonces a Palomino como teniente general y se embarcó para Santo Domingo para ser curado de sus heridas; sin embargo, las condiciones del viaje empeoraron su salud, y los vientos contrarios hicieron que la embarcación tuviera que desviar hacia Cuba, donde murió Bastidas en 1526.
El hijo de Bastidas, también llamado Rodrigo, que era por entonces deán de la catedral, hizo trasladar las cenizas de su padre a Santo Domingo.
Gobierno de Rodrigo Álvarez Palomino Luego de la muerte de Rodrigo de Bastidas, quedó a cargo de la colonia su teniente general, Rodrigo Álvarez Palomino, quien convenció a los demás de la necesidad de conservar la paz sólo con las tribus indígenas vecinas, para no carecer de víveres, y hacer la guerra con otras más distantes como los zaca y los chairama. En consecuencia, se efectuaron varias entradas a la selva, donde los hombres de Palomino realizaron muchos saqueos y capturaron a un buen número de nativos, a los que vendieron como esclavos a Santo Domingo. Luego efectuó Palomino una entrada a las tierras montañosas de los bondas, de donde bajó derrotado, con pérdidas de numerosos hombres.
Gobierno compartido entre Palomino y Badillo