Perdut el favor reial com a conseqüència del desgovern colonial, Cristòfor Colom va trigar més de dos anys en organitzar una tercera expedició cap al Nou Món. Tanmateix, l’entrevista que va mantenir amb els Reis Catòlics després de retornar a Castella, celebrada a Burgos, va ser cordial i en ella va acordar-se prioritzar l’evangelització de les Índies en vista del poc or trobat pels expedicionaris. Igualment, els monarques van alentir el retorn de Colom a Amèrica per dedicar-se a donar instruccions sobre l’organització dels dominis colonials. A més, van començar a aparéixer les primeres veus que afirmaven que l’almirall en realitat no havia arribat a l’Àsia.
L’èxit del viatge de John Cabot des d’Anglaterra fins a la península de Labrador (1497) i l’inici de l’expedició portuguesa de Vasco da Gama en el seu intent de circumval·lar Àfrica per arribar a la Índia van accelerar la nova expedició colombina, la qual tindria per objectiu arribar finalment a terra ferma. Així, el 30 de maig de 1498, Colom va marxar a Amèrica per tercera vegada.
L’expedició comptava amb una flota de vuit naus, en la qual, a més de la tripulació, viatjaven trenta dones. Dos d’aquests vaixells van reforçar les colònies aixecades a La Española, i la resta van dedicar-se a realitzar tasques exploradores a Amèrica del Sud. Amb aquesta expedició, Colom va recórrer Trinitat, la costa veneçolana de Paria i la desembocadura de l’Orinoco, lloc on va situar el paradís terrenal. Finalment, Colom havia topat amb terra ferma.
Retornat a La Española, l’agost de 1498, Colom va trobar-se amb una situació caòtica. El govern de Bartolomé Colón havia estat desastrós: havia entrat en guerra contra els cacics de Xaraguá i Neiva, havia imposat el tribut en cotó als indígenes i havia desprotegit La Isabela (on van morir més de 300 colons). Tot i la derrota dels cacics indígenes, Colom va haver d’enfrontar-se a la rebel·lió dels colons, capitanejats per Francisco Roldán.
Roldán i els seus seguidors van assaltar els magatzems d’armes i subsistències i van recórrer l’illa sumant uns 115 colons en la seva lluita contra Colom. L’almirall va ordenar el procés contra Roldán i va intentar pactar la seva rendició. Segons Las Casas, Colom “escribió a Sus Altezas que le suplicaba que enviasen juez pesquisidor, para que hiciese información de los delitos e insultos y levantamiento del dicho Roldán y de sus secuaces, y también juez que tuviese cargo de la administración de la justicia”.
Mentre s’esperava la resposta de la monarquia, Colom va pactar la rendició de Roldán: quinze dels revoltats podrien retornar a la Península, els que romanguessin a l’illa rebrien terres i tindrien el dret a emprar els indígenes per a explotar les mines i les explotacions agràries, tots els rebels rebrien el perdó i Roldán seria confirmat com a Alcalde. D’aquesta manera, l’almirall, en el seu intent de pacificar La Española, va veure’s obligat a acceptar les condicions imposades per Roldán. Tot i això, els desordres a l’illa no van acabar. Per exemple, Adrián de Moxica va protagonitzar un nou intent de rebel·lió i Colom va fer-lo executar juntament amb els seus seguidors.
Davant les informacions que arribaven des del Nou Món, el 1499, els Reis Catòlics van decidir enviar-hi a Francisco de Bobadilla, comendador de Calatrava, amb funcions de governador. Segons Fernández de Oviedo “no le mandaron prender al Almirante, ni había venido sino por juez de residencia, y para informar del alzamiento de Roldán y de sus consortes. Pero en fin, mandándoselo o no, él prendió al Almirante e sus hermanos y los envió a España. Y quedó con el cargo y gobernación de aquesta isla este caballero, e la tuvo en mucha paz e justicia fasta ek año de mil e quinientos y dos años”.
Efectivament, Bobadilla, arribat a Amèrica l’agost de 1500, va actuar com a jutge del govern colonial i va aturar les execucions dels rebels. Davant l’enfrontament que les seves accions van provocar amb Colom i els seus seguidors, Bobadilla va destituir de les seves funcions a l’almirall i als seus germans Diego i Bartolomé Colón. Igualment, el nou governador va confiscar els béns de l’almirall.
Segons la narració de Las Casas:
[Colom] no podía creer que los Reyes tales cosas hubiesen proveído, por las cuales así totalmente lo quisiera deshacer, sin haber de nuevo en cosa ofendido, antes obligándolos con nuevos trabajos, el descubrimiento de tierra firme y las perlas de Paria […]. Que él era el virrey y gobernador general y que las provisiones y poderes que el comendador traía no eran sino para lo que tocaba a la administración de la justicia; y por tanto requirió al mismo alcalde que el gobernador enviaba, y a la otra gente del Bonao, que se juntasen con él y a él obedeciesen en lo universal, y al comendador en lo que le perteneciese como a juez y administrador de justicia y que todo lo que respondió fue por escrito.
Tot i aquest intent de desafiar el nou governador, i amb ell a l’autoritat dels Reis Catòlics, Colom va acabar acceptant la nova situació. Consolidada la seva posició, Bobadilla va realitzar la seva investigació: Colom era acusat de tirania, crueltat i maltractament dels colons de La Isabela, assassinat dels colons rebels, esclavització dels indígenes i entorpiment de tasca d’evangelització. El desgovern americà era un fet, i els Reis Catòlics van trobar en ell la justificació perfecta per anular les Capitulacions, allunyant definitivament a Colom del monopoli de la conquesta i la colonització del Nou Món.
Finalment, Cristòfor Colom va ser arrestat, juntament amb els seus germans Diego i Bartolomé, i enviat cap a Castella encadenat. L’almirall, certament desequilibrat, va atribuir el seu fracàs de govern a la intervenció del diable mentre planejava un atac atlàntic contra l’Islam per a protagonitzar la reconquesta de Jerusalem en nom dels Reis Catòlics. En aquests moments, Colom seguia convençut de la seva arribada a Àsia. L’almirall va arribar emmanillat a Cadis el 25 d’octubre de 1500. Tot i que els monarques van restituir-li les seves rendes, aviat es veuria desposseït dels seus càrrecs de govern al Nou Món. Tanmateix, ja estava planejant una nova expedició.