thumb|upright=1.5|Trajets des conquistadors en Nouvelle-Grenade. Alonso de Ojeda (1499-1501) Vasco Núñez de Balboa (1513) Pedro Arias Dávila (1513-1519) Pascual de Andagoya, Diego de Almagro et Francisco Pizarro (1515-1529) Pedro de Heredia et ses lieutenants (1532-1538) Sebastián de Belalcázar (1533-1539) Lieutenants de Sebastián de Belalcázar (1533-1539) Gonzalo Jiménez de Quesada (1536-1538) Nicolás de Federmán (1537-1539)
La conquête espagnole de la Nouvelle-Grenade (actuels pays de Colombie) se réfère à la période de conquête entreprise par l'Espagne en Amérique, depuis la découverte de cette dernière par Christophe Colomb en 1492 jusqu'à l'établissement des première autorités centrales régissant ce territoire pour le compte de la Couronne espagnole.
L'autorité juridique, la Real Audiencia de Santa Fe de Bogota, est créée par real cédula en 1549. Elle régit le Royaume de Nouvelle-Grenade, créé en 1550, pour le compte du Conseil des Indes, à Madrid.
L'archevêché de Bogota est créé en 1564. Son autorité religieuse s'étend de Cuenca, au sud de Quito, jusqu'à Panama.
Historique Exploration de la côte caraïbe (1499-1507) thumb|left|upright=0.75|Portrait d'Alonso de Ojeda.
thumb|upright=1.5|Voyages d'Alonso de Ojeda en Amérique.
Le premier espagnol à atteindre la côte de ce qui est aujourd'hui la Colombie, en 1499, est Alonso de Ojeda, compagnon de Colomb lors de son deuxième voyage. À la tête d'une expédition, il explore l'île de Trinidad, celle de Margarita, la côte nord de l'Amérique du Sud auquel il donne le nom de Venezuela, le lac Maracaibo et aborde le cabo de la Vela, sur la côte de la péninsule de Guajira Soledad Acosta de Samper, Biografías de hombres ilustres ó notables, relativas á la época del descubrimiento, conquista y colonización de la parte de América denominada actualmente ee. uu. de Colombia — Alonso de Ojeda. Le cartographe basque Juan de la Cosa et le pilote italien Amerigo Vespucci font également partie de ce voyage, mais les marins n'ont alors pas débarqué. En publiant le récit de ce voyage , Vespucci laissera son prénom à ce nouveau continent dont il sera l'un des premiers à affirmer publiquement l'existence.
La première exploration détaillée des côtes colombiennes est effectuée par Rodrigo de Bastidas, un autre ancien compagnon de Colomb. Parti d'Espagne en 1501 en association avec Juan de la Cosa, il emmène avec lui Vasco Núñez de Balboa, futur « découvreur » de l'océan Pacifique Soledad Acosta de Samper, Biografías de hombres ilustres ó notables, relativas á la época del descubrimiento, conquista y colonización de la parte de América denominada actualmente ee. uu. de Colombia — Rodrigo de Bastidas. Au cours de cette expédition sont reconnus la Sierra Nevada de Santa Marta, le río Grande de la Magdalena, la baie de Carthagène des Indes, le río Sinú, et peut-être le golfe d'Urabá.
L'année suivante, Ojeda est nommé par la Couronne espagnole gouverneur de l'île (la couronne n'étant pas encore persuadée qu'il s'agit bien d'un continent) de Coquibacoa (nom que les amérindiens locaux donnent à l'actuelle péninsule de Gajira). Près de l'actuelle baie Honda, il fonde en Santa Cruz, première agglomération espagnole sur le continent, abandonnée au bout de quelques mois.
En 1504, une expédition de Juan de la Cosa et une autre de Cristóbal Guerra achèvent l'exploration des côtes.
Premiers établissements : Santa María et Panama (1508-1524)
Il faut attendre 1508 pour que la Couronne espagnole accorde des capitulacións qui autorisent non seulement l'exploration mais aussi la fondation de villes et la construction de forteresses. Les deux premières sont accordées à Alonso de Ojeda, qui connaît déjà la région, et Diego de Nicuesa, un riche colon d'Hispaniola. Tous deux sont nommés gouverneurs pour quatre ans, et se voient attribuer deux cents hommes de Castille, six cents Espagnols d'Hispaniola, quarante Indiens et quarante esclaves. Les deux expéditions ne sont pas du goût des autorités de Saint-Domingue, en raison des hommes ponctionnés sur la faible population blanche de l'île et de leur mandat sur l'île de Jamaïque, qui doit servir de base de ravitaillement aux deux hommes. De plus, la frontière entre les deux gouvernorats est mal définie et provoque des disputes, réglées seulement en 1510 lorsqu'elle est fixée sur le río Atrato au fond du golfe d'Urabá. Ojeda devient gouverneur de la Nouvelle Andalousie, à l'est, et Nicuesa celui de la Castille d'Or, à l'ouest.
thumb|upright=0.75|Frontispice de Vasco Nuñez de Balboa de Frederic A. Ober (New York, Harper, 1906)
Parti de Saint-Domingue en 1509, Ojeda fonde San Sebastián de Urabá sur la côte orientale du golfe d'Urabá. L'hostilité des Indiens de la région et le maigre butin pousse les hommes d'Ojeda à expulser ce dernier et à placer à leur tête Vasco Núñez de Balboa.
Abandonnant rapidement San Sebastián, les conquérants établissent une nouvelle ville sur la côte occidentale du golfe, Santa María la Antigua del Darién, première véritable ville du continent, avec une administration, une église et un couvent Soledad Acosta de Samper, Biografías de hombres ilustres ó notables, relativas á la época del descubrimiento, conquista y colonización de la parte de América denominada actualmente ee. uu. de Colombia — Vasco Núñez de Balboa, qui durera une quinzaine d'années (jusqu'à ce qu'elle soit éclipsée par Panama, fondée en 1519). Parvenant à coexister plus ou moins pacifiquement avec les Indiens locaux, Vasco Núñez de Balboa apprend l'existence d'une autre mer au sud de la région où ils se trouvent. Le , après trois ans d'exploration pénible, Balboa découvre l'océan Pacifique, longtemps appelée « Mer du Sud ».
La fondation de la ville, toutefois, est illégale, Balboa n'ayant pas d'autorisation de la Couronne. Aussi celle-ci envoie une puissante flotte de deux mille hommes commandés par Pedro Arias Dávila. Balboa est arrêté et est exécuté pour rébellion en 1519. La même année, Dávila fonde une nouvelle ville, Panama, à l'endroit où l'isthme est le plus étroit, ce qui entraîne l'abandon progressif de Santa María, acté en 1524.
Sur la côte Pacifique, l'exploration est lente. Elle se fait d'abord vers l'ouest et les terres déjà connues du Mexique et de l'Amérique centrale. En 1522, le basque Pascual de Andagoya entend parler pour la première fois d'une riche contrée appelée « Birú » (Pérou). Blessé, Andagoya laisse l'exploration de la région à Diego de Almagro et Francisco Pizarro. Ils explorent la côte Pacifique, très insalubre, pendant quatre ans. En 1529, ils arrivent à l'île du Coq, dans la baie de l'actuelle ville de Tumaco.
Installation sur la côte caraïbe : Santa Marta et Carthagène (1524-1536)
Après le voyage de Fernand de Magellan (1519-1522), il devient clair que l'Asie se trouve bien plus loin que ce que l'on croyait. L'intérêt pour le passage à travers le continent américain et donc pour la région de Panama décline donc brutalement. Toutefois le fabuleux butin ramené par Hernán Cortés à la suite de la conquête du Mexique (1519-1521) ravive cet intérêt.
thumb|upright=0.75|left|Portrait de Rodrigo de Bastidas.
En 1524, l'ancienne juridiction d'Ojeda est divisée en deux gouvernorats concédés à des gouverneurs chargés de les coloniser et de les explorer. À l'ouest du río Magdalena, le bénéficiaire ne prit jamais possession de son mandat mais à l'est, entre le Magdalena et le cap de la Vela, Rodrigo de Bastidas fonde en 1526 la ville de Santa Marta.
La situation politique de la nouvelle colonie devient vite complètement chaotique. Bastidas est assassiné par ses hommes en raison de la pauvreté de la région. Ceux-ci s'opposent aux autorités de Saint-Domingue, qui elles-mêmes se disputent le mandat. Les expéditions se multiplie de façon anarchique, commandées par des sous-fifres brutaux qui s'aliènent complètement les indigènes Tayronas qui peuplent la région et se vengent en pratiquant la politique de la terre brûlée. Toutefois, ces expéditions permettent de trouver un accès à l'intérieur des terres via le río Magdalena, dont le delta est impraticable à cause du courant et des marécages. En 1531, le mulâtre Pedro de Lerma, fils de García de Lerma, gouverneur de Santa Marta, contourne la Sierra Nevada de Santa Marta et atteint le cours moyen du Magdalena Mattew Restthall, Black conquistadors : Armed africans in the early spanish America, Pennsylvania State University. En 1533 est découverte une voie accessible aux bateaux. En 1531, le gouverneur Ambrosio Alfinger, venu du Venezuela, explore la région de l'actuel département de Norte de Santander et en rapporte l'existence d'une riche culture dans les montagnes Soledad Acosta de Samper, Biografías de hombres ilustres ó notables, relativas á la época del descubrimiento, conquista y colonización de la parte de América denominada actualmente ee. uu. de Colombia — Ambrosio de Alfínger.
thumb|upright=0.75|Statue de Pedro de Heredia à Carthagène des Indes.
En 1533, Pedro de Heredia, un des anciens gouvernants de Santa Marta, fonde Carthagène des Indes, à l'ouest de l'embouchure du Magdalena Soledad Acosta de Samper, Biografías de hombres ilustres ó notables, relativas á la época del descubrimiento, conquista y colonización de la parte de América denominada actualmente ee. uu. de Colombia — Pedro de Heredia. Rapidement, dans la région du río Sinú sont découvertes de nombreuses tombes de caciques, riches en or et signalées par des tumuli, qui attirent nombre de conquérants. Après le retour de Francisco Pizarro du Pérou en 1533, Carthagène devient également une escale privilégiée sur la route du Pérou.
La nouvelle de la découverte de la riche région du Pérou et l'arrivée du trésor de l'Inca Atahualpa à Panama à l'automne 1533 provoquent de nombreuses défections, les conquérants préférant se rendre là-bas. Santa Marta est pratiquement abandonnée, ne comptant plus que douze habitants espagnols en 1546, mais Carthagène profite de sa situation de ville-escale pour lancer des expéditions essayant de trouver une voie terrestre vers le Pérou car l'on croit alors que celui-ci se trouve juste au sud de l'embouchure du Magdalena et commencent à circuler des rumeurs sur de riches régions sur le continent, les Dorados. Les expéditions se multiplient à partir de 1534 mais c'est de Santa Marta que part celle qui aboutit à la conquête de la région de Bogota.
Conquête de l'intérieur (1536-1539)
upright=0.8|thumb|Portrait de Gonzalo Jiménez de Quesada.
En 1535, la Couronne espagnole, qui s'inquiète du dépeuplement de la côte caraïbe au profit du Mexique et du Pérou, nomme un nouveau gouverneur à Santa Marta, Pedro Fernández de Lugo, qui était aussi gouverneur des iles de Tenerife et de La Palma dans l’archipel des Canaries.
Fernandez arrive à Santa Marta dans les premiers jours de à la tête d’une armée d’environ 1000 hommes. Le débarquement d’une si grande quantité de gens dans une ville pratiquement abandonnée et déjà aux prises avec une pénurie alimentaire obligea le nouveau gouverneur à presque aussitôt diriger ses hommes vers les villages autochtones de la Sierra Nevada voisine afin de leur réclamer des vivres ainsi que de l’or. Il avait en effet un impérieux besoin de rembourser les propriétaires des navires qui avaient transporter son armée.
Subissant les exactions des Espagnols depuis l’assassinat du fondateur de Santa Marta, Rodrigo de Bastidas, en 1527, les habitants du village de Bonda refusèrent d’obtempérer aux demandes du gouverneur de Lugo et engagèrent le combat. Malgré ce qui sembla être une victoire militaire des envahisseurs, l’opération s’avéra être un échec, car les indigènes avaient évacué femmes et enfants et vidé leurs greniers avant l’arrivée de l’armée du gouverneur.