In June 1978, Mike Rendina of Paradise Restaurant Co. Ltd. applied for and received a liquor permit for a 100-seat dining room and 50-person cocktail lounge at this location. For years the space had been home to a pharmacy. Its last incarnation was Midgie's Drug Store.
October 4, 1978, Winnipeg Tribune
The first grand opening ad for Paradise appeared in local papers on October 4, 1978. It was run by Mike and Dina Rendina and employed other family members.
Marian Warhaft, The Free Press’ long-time food critic, visited just a couple of weeks after it opened and wrote: "An enormous sign stretches across the top of the recently opened Paradise Restaurant, 789 Portage Avenue. You can’t miss it and, if you’re fond of Italian food, you shouldn’t. The place is big, solid and comfortable with carpeted floors and scarlet napery on the well spaced tables."
The family opened a second location on Leila Avenue in 1983. It remains open.