飲食店、キャバレー、喫茶店など手広く商売をしていた実業家により[9]、1948年に創業された[2][3][4]。後年に知られるような内装になったのは1980年代前半といわれる[9]。
店内の天井の中央に飾られた大きなシャンデリアを始めとして[10]、紅色のビロードのソファ[2]、重厚感のあるテーブル[6]、天井が高いために狭苦しさを感じさせない空間[1]、古き良き時代を感じさせる上品な内装が特徴であった[10]。花園地区は小樽の観光ルートに組み込まれることは少ないが、地元民のための酒屋が建ち並ぶ歓楽街でもあるために、昭和の雰囲気のある飲食店街は懐古趣味の人向けであり、コロンビアもその一つであった[3]。学生時代にこの内装に憧れて来店し、成人後にその思い出を懐かしんで来店する客も多かった[10]。
喫茶店のメニューとしては、食事からデザート、飲み物まで、非常に豊富なことが特徴であった[1]。オムライスやナポリタン、ドリア、ハンバーグなどの洋食はもちろん、和食では丼物や弁当まで用意されていた[6]。インスタント食品やレトルト食品を一切使わず、手作りの味にも拘っていた[10]。中でもチョコレートパフェは創業当時からの看板商品であり[2][7]、花園で酒を楽しんだ後にコロンビアのパフェを食べるのが小樽市民の定番との声、「元祖シメパフェ」との声もあった[2]。コーヒーにソフトクリームを乗せたモカソフトもまた看板商品の一つであり、女性客の一番人気のメニューであった[11]。オムライスを毎日食べに来る客もいた[10]。材料や味つけなど[10]、時代に合わせて内容を改良することはあっても、創業当初からの品揃えはほとんど変えないことが心がけられていた[6]。
近隣に酒場の多い立地であり、夜遅くまで営業していたため、女性客を中心として二次会の会場として利用されることや[11]、食事の後やスナックに行く前に立ち寄る客も多かった[12]。年配の女性客が多く訪れるため、会話の合間にタイミングを見つけて声をかけたりする気配りなど、くつろげる空間を提供することを大切なサービスとしていた[10]。
2004年（平成16年）には、1960年代から1970年代に流行した歌声喫茶の再現のため、小樽市内の年配者を中心した歌声喫茶サークルにより利用されて、年配者を中心に静かな人気を博した[13]。
著名人では、小樽出身のタレントである加藤浩次が、テレビ番組「がっちりマンデー!!」(TBS)で「よく行っていた」と発言していた[14]。小樽出身の漫画家である山花典之も「私の青春時代の思い出のある場所」と語り、自身が原作を担当した漫画『聖樹のパン』にも、この店を登場させていた[15]。
2023年時点では3代目店主夫妻が経営していたが、店主の妻が入院、1人残った店主も高齢で、体力的に経営続行が困難となったため[16]、2023年8月31日で閉業した[5][8]。閉業の報せは、前日の8月30日に密かに入口に貼り紙を貼ったのみにもかかわらず、その情報はSNSや口コミで急速に広がり、閉業当日には多くの小樽市民が殺到し、入口前にも入店を待つ人々が長蛇の行列をなし、閉業を惜しんだ[5][16]。建物は2025年4月から6月頃までに解体され時間貸し駐車場となっている[17]。
