Kino Polonia zostało utworzone w latach 1936-1939 jako część hotelu Viktoria oraz towarzyszącej mu restauracji. 

Sam hotel został utworzony w 1865 roku przez Emila Lindemanna przy ówczesnej ulicy Gęsiej 13. Od tego czasu obiekt sukcesywnie rozbudowywano. W momencie otwarcia sali kinowej ulica nosiła już obecną nazwę – Przechodnia.

Jak donoszą gazety rozpisujące się o inwestycji, „wejście obok hotelu Viktoria prowadziło do westybulu oraz poczekalni wspaniale urządzonej”. 

Sala kinowa była imponująca – według zapewnień prasowych, liczyła 750 miejsc parterowych. Była również bardzo wysoka. Została wzniesiona na planie pięcioboku, co miało umożliwić lepszą widoczność ekranu z każdego kąta sali. Widownia natomiast była zbudowana na kształt tuby, rzędy siedzeń ułożone zaś wachlarzowo – wszystko to, by uczynić oglądanie filmu jeszcze bardziej komfortowym. Sala kinowa była również wyposażona w mechaniczną wentylację.

Wejście do kina znajdowało się przy ulicy Przechodniej, wyjście natomiast od ulicy Przedmiejskiej.

Po II wojnie światowej kino Polonia było najważniejszym i najbardziej reprezentacyjnym włocławskim kinem, w którym grano filmy zaraz po przywiezieniu tytułów z Warszawy.

Często kina zmuszone były wchodzić ze sobą w kooperację i wymieniać się taśmami. Tak działo się we Włocławku między kinem Polonią, a Bałtykiem, które grały film jednocześnie, a w trakcie projekcji goniec krążył między kinami przekazując taśmy.

Oprócz sali kinowej znajdowała się tu elegancka kawiarnia oraz dwa halle: jeden dla palących, a drugi dla niepalących widzów. W latach 90-tych w Polonii można było również kupić popcorn.

Okolica obfitowała w rozmaite lokale gastronomiczne, do których można było udać się po filmie. We wspomnieniach mieszkańców zachowały się przede wszystkim dwa miejsca – Obywatelska oraz Myśliwska.

Kino Polonia zostało zlikwidowane jako ostatnie kino studyjne we Włocławku w 2007 roku. Wówczas na okres dwóch lat, do czasu otwarcia Multikina, Włocławek pozostał bez żadnego obiektu kinowego.

Budynek kinowy został wystawiony na sprzedaż w 2021 roku. Na portalach prasowych pojawiły się wówczas zdjęcia wnętrza Polonii – z ekranem i fotelami kinowymi wciąż na swoich miejscach.