Lâu nay nhắc đến 6 tàu ngầm diesel - điện Đề án 636 mà Việt Nam đặt mua từ Nga, mọi người đều nghĩ ngay đến tên gọi Kilo và cho rằng đây là tên gọi chính thức của loại tàu ngầm phi hạt nhân này. Tuy nhiên, tên gọi Kilo chỉ là định danh mà NATO chỉ định để gọi tàu ngầm diesel - điện Đề án 877 Paltus sản xuất tại Nga vào đầu những năm 1980.
Tên ký hiệu của NATO là tên mật mã phân loại những thiết bị vũ khí quân sự của Liên Xô và Trung Quốc. Nó được tạo ra để thuận tiện cho quá trình liên lạc giữa các đơn vị quân đội nói những ngôn ngữ khác nhau trong khối NATO. Một lý do khác là vì trong nhiều trường hợp, tên thật của thiết bị không thông dụng hoặc trong vài năm đầu khi thiết bị đó được đưa vào sử dụng, phương Tây chưa biết tên thật của nó. Do các thiết bị quân sự được sử dụng trên nhiều nước nên tên ký hiệu của NATO thường được sử dụng rộng rãi.
Tên gốc của tàu ngầm Kilo được đặt theo tên một bài hát nổi tiếng trong cách mạng tháng 10 Nga năm 1917.
Đến giữa những năm 1990, Nga phát triển một biến thể nâng cấp từ tàu ngầm diesel - điện Paltus được gọi là Đề án 636 Varshavyanka, biến thể này được NATO định danh là Improved Kilo (Kilo cải tiến). Tuy vậy, cho tới nay, tên gọi Kilo vẫn được sử dụng chung cho cả tàu ngầm diesel - điện Đề án 877 và 636.
Ngoài tên gọi thông dụng là Kilo, tàu ngầm diesel - điện Đề án 877 và 636 còn được Hải quân Mỹ đặt cho biệt danh “Black Hole” (Hố đen) bởi khả năng hoạt động êm ái trong lòng đại dương và khả năng tiếp cận nhanh chóng tới các biên đội tàu nổi của địch trước khi bị phát hiện.
Theo trang Global Security, tên gọi Varshavyanka của tàu ngầm diesel - điện Đề án 636 được đặt theo tên một bài hát của Ba Lan.
"Varshavyanka" là bản dịch tiếng Nga của bài hát cách mạng Ba Lan (nguyên văn tiếng Ba Lan là “Warszawianka”).
Có hai bài hát mang tên Varshavyanka, bài hát đầu tiên được viết bởi nhà văn người Pháp Casimir Delavigne vào năm 1831. Sau khi được dịch sang tiếng Ba Lan và phổ nhạc, bài hát này được ví như là quốc ca thứ 2 của Ba Lan.
Bài hát Varshavyanka thứ hai được nhà thơ và nhà xã hội học Ba Lan Vatslav Sventsitski (1848-1900) sáng tác vào năm 1879 khi ông phải chịu cảnh tù đày vì hoạt động cách mạng. Bài hát bắt đầu trở nên phổ biến trong giai cấp công nhân và các đảng cộng sản quốc tế trong các cuộc nổi dậy ở Nga năm 1905.
Tàu ngầm Kilo còn được Hải quân Mỹ đặt cho biệt danh “Black Hole” (Hố đen)
Về sau này, bài hát Varshavyanka còn được gọi là “bài ca chiến đấu vĩ đại của người Nga”. Đây là một bài hát rất quan trọng trong và sau cuộc cách mạng tháng 10 Nga năm 1917, bài hát sau đó đã được phổ biến rất rộng rãi và hầu như tất cả mọi người trong các nước hậu Xô Viết đều biết đến nó. Bài hát này thường được gọi là “klassika”(phiên âm tiếng Nga) có nghĩa là “tác phẩm kinh điển”.
Ban đầu, tàu ngầm Đề án 636 được dự định xuất khẩu cho các nước thuộc khối Warszawa. Đây là một liên minh quân sự bao gồm 8 nước Liên Xô, Albania (rút ra năm 1968), Ba Lan, Bulgaria, Đông Đức, Hungary, Romania, Tiệp Khắc, được thành lập năm 1955 nhằm đối phó với khối quân sự Bắc Đại Tây Dương NATO.
Tuy nhiên, chiếc tàu ngầm Đề án 636 Varshavyanka đầu tiên lại được xuất khẩu cho Trung Quốc, một quốc gia không năm trong khối Warszawa, điều này là do ảnh hưởng của cuộc khủng hoảng kinh tế-chính trị giữa Liên Xô và Đông Âu cuối những năm 1980.
Mặc dù, mục tiêu ban đầu của tàu ngầm Đề án 636 Varshavyanka không đạt được như kỳ vọng nhưng không vì thế mà chương trình này không đạt được thành công. Từ khi được giới thiệu, tàu ngầm Đề án 636 Varshavyanka đã nhận được sự quan tâm đặc biệt của Hải quân Nga cũng như nhiều nước khác trên thế giới.
Trung Quốc là khách hàng nước ngoài lớn nhất của tàu ngầm diesel - điện Đề án 636 Varshavyanka với 10 chiếc trong trang bị (2 chiếc đặt mua năm 1996 và 8 chiếc mua năm 2002).
Việt Nam là khách hàng lớn thứ 2 của tàu ngầm Đề án 636 Varshavyanka với 6 chiếc được đặt hàng trong năm 2009. Chiếc đầu tiên trong hợp đồng mang tên Hà Nội sẽ lên đường về Việt Nam vào khoảng trung tuần tháng 11/2013.
Algeria cũng đặt hàng 2 chiếc tàu ngầm loại này và đã được giao hàng đầy đủ. Hải quân Nga cũng đang đặt hàng 6 tàu ngầm Đề án 636 Varshavyanka.
