Florida Marlins

Ab der Spielzeit 1997 war Castillo dann Stammspieler im MLB-Team der Marlins. Zusammen mit Edgar Rentería, beide Spieler waren 21 Jahre alt, stellte er das jüngste Infield-Duo in der Geschichte der National League. Nachdem sich Castillo Mitte 1997 die linke Ferse brach und daraufhin eine halbe Saison ausfiel, wurde er in die Minor League zurückgeschickt und wurde bis August 1998 nur noch sporadisch im Team eingesetzt. Obwohl er aus diesen Gründen keine Einsatzzeit während der World Series 1997 bekam, darf er trotzdem den Titel für sich beanspruchen, da er in der Regular Season ab und zu spielte.

In den folgenden Jahren zeigte Castillo immer stärkere Leistungen. Besonders seine hohe Anzahl an Stolen Bases machten auf ihn aufmerksam. Im Jahr 2000 (62 Stolen Bases) und 2002 (48 Stolen Bases) war er der Beste in dieser Kategorie in der ganzen MLB. 2002 wurde er zudem erstmals zum MLB All-Star Game eingeladen.

In der Spielzeit 2003 gewann Castillo, diesmal als aktiver Teilnehmer, mit seinem Team die zweite World Series. Neben der World Series 2003 konnte er zudem seinen ersten Gold Glove Award gewinnen. Dies konnte er in seinen letzten beiden Jahren bei den Marlins 2004 und 2005 wiederholen.

Minnesota Twins

Am 2. Dezember 2005 wechselte Castillo zu den Minnesota Twins. Er spielte 2006 eine starke erste Saisonhälfte und erreichte zu dieser Zeit seine 300ste gestohlene Base.

In der Spielzeit 2007 erreichte er einen neuen MLB-Rekord, nachdem er 143 Spiele in Folge auf der Second Base ohne Error hinter sich brachte.

New York Mets

Castillo wechselte am 30. Juli 2007 zu den New York Mets, wo er eine sehr starke zweite Saisonhälfte ablieferte. Alleine in den letzten 42 Spielen des Jahres gelangen ihm 34 Runs.

Viele Verletzungen machten 2008 für Castillo zu einem schwierigen Jahr. Er konnte nur 87 Spielen bestreiten, trotzdem konnte er bei 19 Versuchen 17 Bases stehlen.

Nach einer erneut starken Spielzeit 2009 bekam Castillo 2010 relativ wenig Einsätze. Er selbst brachte sich anschließend ins Gespräch für einen Wechsel. Ob die Mets ihn zur Saison 2011 behalten, ist noch offen.