Teledysk Wideoklip do tego utworu, podobnie jak do piosenki „Ven conmigo (Solamente tú)” (wersji hiszpańskojęzycznej), wyreżyserował Paul Hunter w dniach 12–15 czerwca 2000 roku. Choreografię do teledysku stworzyła Tina Landon, wcześniej pracująca już z Christiną Aguilerą przy „What a Girl Wants”. movement-agency.com. [dostęp 2020-04-07].. Klip stał się przebojem MTV i uplasował się na szczytowej pozycji notowania Total Request Live. Za pośrednictwem teledysku Aguilera zmieniła swój image na bardziej pikantny i filuterny. Elizabeth Learned, redaktorka witryny thecelebritycafe.com, uwzględniła wideo w zestawieniu dziesięciu najlepszych teledysków w karierze Aguilery; chwaliła jego kolorystykę, choreografię oraz kostiumy noszone przez wokalistkę i tancerzyLearned, Elizabeth (2014-02-21). „Top 10 Christina Aguilera music videos”. thecelebritycafe.com. [dostęp 2014-09-11].. W 2015 roku witryna bustle.com chwaliła teledysk, nazywając go ważnym dla popkultury i „niedorzecznie wspaniałym”Reilly, Kaitlin (2015-05-07). „9 Times Christina Aguilera’s ‘Come On Over’ Music Video Was Totally Your Lifestyle Goal”. bustle.com. [dostęp 2015-05-07]..