I dag är Vij en av de mest kända kockarna i Kanada, en stamgäst på landets TV-matshower och författaren till bästsäljande kokböcker.
Folk köar runt kvarteret för att äta på hans tre indiska restauranger i Vancouver. Och hans curry färdiga måltider är lagrade i stormarknader över hela landet.
Men all framgång, och hans mångmiljon förmögenhet, nästan inte hände.
När herr Vij 1994 öppnade sin första restaurang i Vancouver, 30 år, innebar hans vägran att servera de standardrätter som fanns i de flesta indiska matställen i Kanada att kunderna var mycket magra på marken.
Och trots att han backades upp av en investering på 23.000 kanadensiska dollar (19.000 kronor; 12.500 pund) från sin far, var restaurangen - Vijs - nära att behöva stänga ner under sina första 12 månader.
Vij, som nu är 50, säger: " Det var som om jag hade nått botten. Jag hade nått den punkt där jag inte hade mer pengar."
Det var så dystert att han var tvungen att uppmuntra kunderna att beställa rätter som hade en högre vinstmarginal.
"Om de beställde en kycklingcurry skulle jag säga "beställ lammet", eftersom jag visste att vinsten på lammet kanske var en dollar mer", säger han.
"Så om i slutet av dagen, även om vi bara tjänade 10 dollar till, var det 10 dollar i min ficka."
Tack och lov fick Vij snart reda på hur viktiga bra recensioner är för restaurangerna.
Under de månader som följde skrev en rad matkritiker mycket positiva recensioner om Vijs, berömmer både sitt exklusiva indiska kök, och den goda servicen. Detta resulterade i att matgäster anlände i allt större antal.
Så mycket att Vij inom några år behövde flytta till en mycket större lokal. Och Mr Vij har aldrig sett tillbaka.
Född i den indiska staden Amritsar till en relativt rik familj, som ett barn Mr Vij ville vara en Bollywood skådespelare, innan gravitation mot en karriär som kock.
19 år lämnade han landet för att träna i klassisk matlagning i Salzburg i Österrike. När han tog examen fick han ett jobb på ett hotell i Banff, en liten stad i den kanadensiska provinsen Alberta, inbäddad i Klippiga bergen.
Det var där han stannade tills han öppnade sin egen restaurang i Vancouver.
Med Vijs fru Meeru Dhalwala också starkt involverad i verksamheten, öppnade en andra restaurang 2004, följt av en tredjedel i Vancouver, och en annan i Victoria, huvudstaden i British Columbia.
Det finns också en flyttbar matvagn som rör sig runt Vancouver, och ett fabrikskök som gör de färdiga måltiderna. Och en ny restaurang kommer snart att öppna på Fairmont Banff Springs Hotel, den första plats som Mr Vij arbetade i Kanada.
I takt med att Vijs restauranger blev allt mer kända började han bjudas in till matlagnings-TV-program, vilket ytterligare ökade hans profil. Han har också varit domare i den kanadensiska versionen av Dragons' Den entreprenörskap show, och med sin fru, skrev två kokböcker.
Han blir lite obekväm när han blir ombedd att tala om hur han hanterar att vara en offentlig person, men medger att befordran är bra för affärer.
"Jag tror att du behöver lite egoism och narcissism", säger han. "Särskilt för någon som är lika mycket av en offentlig person som han är en affärsman.
"Du vet, ditt ansikte och din personlighet är mycket en del av varumärket."
På en daglig basis Mr Vij arbetar nu som framsidan av huset på hans huvud Vij restaurang i Vancouver, möte och hälsningsrestauranger. Han beskriver restaurangerna som sina "babys".
"De är skapade av mig och Meeru, som har gjort ett oerhört bra jobb med att underhålla köket, personalen, damerna, och hantera allt", säger han.
"Så jag är helt involverad i detta, och fortsätter att vara involverad.
"Den dagen jag inte är involverad i mina egna affärer, det är den dagen jag kommer att vara under jorden i princip."
I framtiden vill Vij nu börja sälja sina färdigrätter internationellt... inklusive att exportera dem till Indien.
"Den långsiktiga visionen är att ta min indiska mat... tillbaka till Indien, och säga "Titta, en av dina söner lämnade landet, han åkte till Kanada, han blev framgångsrik, och nu ger han tillbaka till landet samma kärlek och passion."
"Jag tänker alltid på Indien som min mamma. Det skulle vara som att laga mat till min mamma.
"En dag vill jag kunna säga till min mamma att du gav mig all denna kärlek och vård, och jag ger den tillbaka till dig."
Det var en beslutsamhet att aldrig servera kyckling tikka masala som nästan stoppade karriären som kändiskock Vikram Vij precis när han började.