Vučinić pochodzi z Czarnogóry, z 70-tysięcznego miasta Nikšić. Tam też rozpoczynał swoją piłkarską karierę zapisując się do klubu Sutjeska Nikšić, który od paru lat występował w pierwszej lidze Serbii i Czarnogóry. Mirko najpierw grał w zespole juniorów, a do pierwszego zespołu został włączony w sezonie 1999/2000. Długo czekał na swój debiut w lidze. Swój pierwszy mecz rozegrał dopiero w rundzie wiosennej mając zaledwie niespełna 17 lat. W sezonie zagrał tylko 9 meczów, ale zdołał zdobyć 4 bramki, i tym samym pokazał swój nieprzeciętny talent. Te 4 bramki nieznacznie pomogły drużynie Sutjeski w zajęciu wysokiego 5. miejsca w lidze. Utalentowanym młodzieńcem zainteresowało się włoskie US Lecce i latem 2000 wciąż 17-letni Vučinić wyjechał do Włoch. W Serie A w barwach Lecce Mirko zadebiutował 18 lutego 2001 roku w przegranym 0:1 meczu z AS Roma. W swoich pierwszych dwóch sezonach w Serie A Mirko grał mało i rozegrał raptem 8 meczów, ale był wówczas jeszcze zbyt młodym zawodnikiem by móc rywalizować z takimi piłkarzami jak Davor Vugrinec, Cristiano Lucarelli czy Ernesto Javier Chevantón. Próbkę swoich umiejętności mógł pokazać w sezonie 2002/2003 podczas gry Lecce w Serie B. Tam zdobył 5 bramek w 28 meczach, ale najważniejsze, że trener Delio Rossi widział młodego Czarnogórca w pierwszym składzie zespołu. Jednak po powrocie Lecce do Serie A Vučinić znów był tylko rezerwowym i zagrał raptem w 12 meczach ligowych niewiele pomagając swojej drużynie w utrzymaniu się w lidze. Sezon 2004/2005 to wielki popis Vučinicia, który stworzył jeden z najskuteczniejszych ataków w lidze razem z Bułgarem Waleri Bożinowem. Jego 19 bramek w sezonie zamknęło usta wszystkim krytykom, którzy już nie wierzyli w talent Mirko. Po sezonie został przez włoską prasę uznany najlepszym graczem młodego pokolenia w Serie A. Był najlepszym strzelcem swojego zespołu, a w lidze klasyfikacji strzelców uplasował się na 5. pozycji. Więcej bramek od niego zdobyli wówczas tak dobrzy zawodnicy jak Lucarelli, Luca Toni, Alberto Gilardino i Vincenzo Montella. Sezon 2005/2006 nie był już dla Vučinicia i drużyny Lecce tak dobry jak poprzedni. Zdobył 9 goli w 34 meczach, a jego drużyna opuściła szeregi Serie A. Wiadome już było, iż Vučinić nie będzie grać na zapleczu ekstraklasy i latem 2006 najkonkretniejszą ofertę złożyła mu stołeczna Roma. Tuż przed zamknięciem okna transferowego, 30 sierpnia 2006 Mirko podpisał z rzymskim klubem roczny kontrakt z opcją przedłużenia na 4 kolejne. Rocznie miał zarabiać 900 tysięcy euro, zespół Lecce otrzymał za Vučinicia kwotę 3,3 miliona euro. W Romie Vučinić zadebiutował 22 października w zremisowanym 1:1 ligowym pojedynku z Chievo Werona. 11 stycznia 2009 roku strzelił dwa gole w zremisowanym 2:2 spotkaniu Serie A przeciwko Milanowi.