Après la saison 1995, le vétéran des Yankees devient agent libre et rejoint pour 1996 les Angels de la Californie, renommé Angels d'Anaheim la saison suivante. Durant la campagne 1999, les Angels transfèrent Velarde aux Athletics d'Oakland. Cette année est la meilleure de Velarde en carrière: en 156 matchs au total avec deux clubs, il prend le 4erang de la Ligue américaine avec 200 coups sûrs[3], finit premier des majeures avec 152 simples[4], réalise des sommets personnels de 16 circuits, 105 points marqués et 76 points produits, et maintient une moyenne au bâton de ,317. Il aide Oakland à atteindre les éliminatoires et produit 3 points avec 5 coups sûrs en 5 matchs de Série de division contre son ancien club, les Yankees.
En , les Athletics d'Oakland l'échangent aux Rangers du Texas pour le lanceur Aaron Harang. Son séjour avec ce club ne dure pas un an puisqu'il est rapatrié par les Yankees durant l'été 2001, dans l'échange qui envoie au Texas le releveur gaucher Randy Flores et le lanceur droitier Rosman García. Entre 1996 et 2000, les Yankees remportent la Série mondiale quatre fois en cinq ans: Velarde, qui a quitté peu avant le premier de ces titres, revient à temps pour participer à la Série mondiale 2001, mais New York perd contre Arizona. Velarde met fin à sa carrière en 2002 par un dernier passage à Oakland.
