There exists a class of ultralight Dark Matter (DM) models which could form a Bose-Einstein condensate (BEC) in the early universe and behave as a single coherent wave instead of individual particles in galaxies. We show that a generic BEC DM halo intervening along the line of sight of a gravitational wave (GW) signal could induce an observable change in the speed of GW, with the effective refractive index depending only on the mass and self-interaction of the constituent DM particles and the GW frequency. Hence, we propose to use the deviation in the speed of GW as a new probe of the BEC DM parameter space. With a multi-messenger approach to GW astronomy and/or with extended sensitivity to lower GW frequencies, the entire BEC DM parameter space can be effectively probed by our new method in the near future.