Vsevolod Veličkovskij nasce in Ucraina nella città di Stanislavov (attualmente Ivano-Frankovsk) il 1° giugno 1903 da una famiglia di sacerdoti per tradizione, di origine cosacca. Terminate le scuole medie entra all’Istituto San Iosafat, diretto dai monaci basiliani. Durante la Prima Guerra Mondiale Veličkovskij fa parte della Guardia imperiale ucraina, creata all’interno dell’esercito austro-ungarico. Dal 1920 studia al seminario diocesano di Leopoli, nel 1924 entra nel noviziato e nel 1925 nel monastero di Golosko, non lontano da Leopoli, pronuncia i voti nella Congregazione del Santissimo Redentore e assume il nome monastico di Vasilij.
Il 9 ottobre 1925 Vasilij è ordinato sacerdote e lavora come insegnante e missionario in Volynija. Nel 1927 viene trasferito nel monastero di Stanislavov, dove opera un consistente gruppo di missionari guidati da padre Iosif de Bocht, a sua volta grande figura di missionario. In questo periodo si aprono nuove possibilità per un lavoro apostolico in Volynija, che era stata annessa alla Polonia nel 1921: inizia una migrazione di massa di ucraini dalla Galizia alla Volynija; padre Nikolaj Čarneckij e padre Grigorij Šiškovič si occupano della cura spirituale dei nuovi arrivati. In seguito, quando nel 1928 padre Šiškovič lascia il paese per assistere gli ucraini del Canada, al suo posto viene destinato padre Veličkovskij. Durante il suo lavoro in Volynija questi promuove la costruzione di venti cappelle. Avendo un’indole lieta, riesce in breve tempo ad instaurare rapporti amichevoli con i fedeli e i sacerdoti ortodossi. È in buoni rapporti con la famiglia della poetessa ucraina Lesa Ukrainka.
Padre Veličkovskij ottiene persino di incontrarsi con il maresciallo J. Pilsudskij, capo dello Stato polacco. Nel 1930, con il permesso del maresciallo, riesce ad adattare una chiesa di rito latino della città di Kovel alla celebrazione in rito greco-cattolico. Tuttavia, i successi del missionario vengono interpretati come un ostacolo alla polonizzazione degli ucraini in Volynija. Per questo motivo nel 1935, su richiesta delle autorità polacche, Veličkovskij deve lasciare la Volynija e tornare nel monastero di Stanislavov. Qui si mette a lavorare con l’energia che gli è propria, e collabora creativamente con un altro grande predicatore, padre Zenovij Kovalik.
Nel 1936 Veličkovskij è uno dei principali relatori al convegno sull’Unità indetto dalla Chiesa greco-cattolica ucraina a Leopoli. Intervenendo al convegno parla della sua esperienza di lavoro con gli ortodossi sulla possibilità dell’unione delle Chiese e sottolinea la necessità di attenersi scrupolosamente alla tradizione orientale nella celebrazione liturgica e nella predicazione. Nel 1938 pubblica un almanacco per il venticinquesimo anniversario dell’attività missionaria dei redentoristi in Ucraina. Qui troviamo una dedica affettuosa e cordiale alla mamma che dimostra tutta la sua tenerezza figliale e il suo credo: «Sii benedetta, o mamma, che hai sacrificato tuo figlio al popolo. Egli è morto al mondo, ma il suo sacrifico non è stato vano per Dio e per il popolo. Egli è vivo e vivrà e darà vita a milioni, perché lui, tuo figlio, è missionario di Gesù e Maria, è Redentorista».
Sogno di Veličkovskij è di costruire a Stanislavov una splendida chiesa in onore della Madre di Dio. Il sacerdote si distingue per la grande devozione e l’amore alla Vergine, diffonde con particolare impegno la devozione all’icona della Madre di Dio del Perpetuo Soccorso che, per il suo stile orientale, unisce i greco-cattolici e gli ortodossi. Veličkovskij riesce a raccogliere una somma sufficiente per la costruzione della chiesa, compera il materiale necessario, ma il ministro per gli affari bellici di Varsavia non permette ai redentoristi di erigerla, e limita così il loro influsso sugli abitanti del posto, temendo che i cattolici orientali contrastino il rito latino, visto dai governanti come un modo per polonizzare la popolazione. La Volynija, infatti, era stata unita alla Polonia nel 1921.
Nel 1939, dopo l’occupazione dell’Ucraina occidentale da parte dell’esercito sovietico, Veličkovskij viene arrestato per la prima volta dall’NKVD, la polizia politica, per aver organizzato una processione durante la festa della Madre di Dio Addolorata. La processione viene considerata come una forma di propaganda religiosa, proibita in URSS. Causa dell’arresto è che i soldati sovietici che si trovano in città, incontrando la processione, si tolgono il berretto e fanno il segno della croce. Dopo breve tempo Veličkovskij viene tuttavia liberato.
Nel 1941, durante l’occupazione sovietica nel corso della seconda guerra mondiale, per incarico del Metropolita Šeptickij e su invito della comunità ortodossa, Veličkovskij giunge nella città di Kamenec-Podol’skij. I fedeli gli offrono la chiesa di San Nicola per la celebrazione della Divina Liturgia, ma le autorità tedesche gli impongono, pena la fucilazione, di abbandonare la città entro 24 ore. Nel 1944, quando l’armata Rossa nelle vicinanze di Ternopol’ deve sostenere battaglie furibonde contro i tedeschi, si viene a sapere che in Ternopol’ non esiste neppure un sacerdote che possa assistere i fedeli. Nonostante il pericolo, Veličkovskij, di sua volontà, decide di recarsi a Ternopol’. Dopo essere diventato igumeno del monastero di Ternopol’, Veličkovskij nella notte fra l’11 e il 12 aprile 1945 (secondo altri dati il 26 giugno 1945) viene arrestato a trasferito a Kiev. Il tribunale di guerra lo condanna alla pena capitale «per attiva propaganda antisovietica» durante le prediche e nelle pubblicazioni. La pena viene commutata a 10 anni di lager. Veličkovskij viene rinchiuso nel lager di Vorkuta, dove la temperatura scende fino a 50° sotto zero e i detenuti sono costretti a dormire uno sopra l’altro per non morire assiderati. Il sacerdote celebra la Liturgia nelle condizioni più disperate, nelle gallerie fuori uso delle miniere, dove si riunisce con una ventina di detenuti alle 4 del mattino.
Nel 1953 Veličkovskij viene accusato di aver organizzato uno sciopero dei detenuti e per questo viene trasferito al carcere di Vladimir, ma qui riesce dimostrare la propria innocenza e quindi viene rimandato in lager. Nel 1955, scontata la pena, ritorna a Leopoli, dove partecipa all’organizzazione della vita della chiesa clandestina greco-cattolica. In seguito scriverà nelle sue memorie: «I dieci anni di reclusione sono passati in modo straordinariamente veloce ed ecco che ora i miei piedi possono camminare per le vie dell’amata Leopoli». Dopo la liberazione viene in contatto con gli altri confratelli redentoristi. Nelle condizioni di un’esistenza catacombale insegna ai giovani studenti del seminario clandestino, celebra in appartamenti privati e si occupa della cura spirituale delle suore basiliane.
Nel 1959 papa Giovanni XXIII designa Vasilij Veličkovskij vescovo della chiesa clandestina in Ucraina. Ma in quel periodo su tutto il territorio dell’URSS non esiste nessun vescovo greco-cattolico in libertà che possa consacrarlo. Ciò è possibile soltanto il 4 febbraio 1963, quando il metropolita Slipyi, liberato dalla prigione e trovandosi per tre giorni a Mosca prima di essere espulso dall’URSS, chiama con un telegramma Veličkovskij per potersi confessare. La consacrazione avviene segretamente nell’albergo Moskva. Il neoconsacrato riceve il titolo di vescovo di Luck. Il vescovo Veličkovskij ritorna a Leopoli e diventa capo della chiesa del silenzio in Ucraina. Consacra segretamente 40 nuovi sacerdoti. Scrive un libro sulla venerazione dell’immagine della Madre di Dio del Perpetuo Soccorso e riesce a diffonderlo clandestinamente. Per questo il 2 gennaio 1969 viene arrestato e condannato a 3 anni di prigione nella città di Kommunarsk nel Donbas. Scontata la pena, nel 1972 viene espulso dall’URSS. Passa qualche tempo a Roma, dove è ricevuto da Paolo VI e dal cardinale Slipyj. Su invito del metropolita Maksim Germanjuk si trasferisce in Canada, celebra in diverse chiese greco-cattoliche sia in Canada che negli Stati Uniti.
Muore a Winnipeg (Canada) il 30 giugno 1973. Secondo alcune testimonianze, alla fine del secondo arresto, nel 1972, il vescovo Veličkovskij sarebbe stato costretto a subire un’iniezione di veleno ad azione ritardata.
Il vescovo Vasilij Veličkovskij è stato beatificato il 27 giugno 2001, assieme ad altri 24 greco-cattolici vittime del regime sovietico, durante la visita in Ucraina di papa Giovanni Paolo II.