Rebello comenzó tocando el piano clásico a la edad de nueve años, se interesó por el folk y el soul, y a la edad de 16, tras oír a Herbie Hancock, se inclinó por el jazz.
Con 19 años se convirtió en el primer músico de jazz en asegurarse una plaza de estudiante en la England's Guildhall School of Music and Drama.
Ganó experiencia como acompañante de un surtido grupo de estrellas americanas como James Moody, Bud Shank, Art Blakey, Gary Burton, Branford Marsalis y Wayne Shorter y músicos ingleses de la talla de Tommy Smith, Jeff Beck, Cleveland Watkins Steve Williamson y Alec Dankworth.
Durante los años 1980 formó diversos grupos que se movieron en la escena acid jazz británica.
Además de ello, en los 90 no tuvo reparo en liderar un trío acústico y una banda eléctrica a lo Chick Corea, mostrando también su querencia por el R&B y la música Soul.