Заложен и построен през 1985 г. в полската от корабостроителницата „Северна корабостроителница“ в Гданск.
От 1985 до 1996 г. влиза в състава на Черноморския флот на СССР и Украйна, изпълнявайки задачи по отработка на стоварване на морски десант и носи служба в Средиземно море.
В края на 1993 – началото на 1994 г. взема участие заедно с други кораби от бившия Черноморски флот на СССР по евакуацията на бежанци от зоната на грузино-абхазския конфликт. Според думите на корабния медик, Михаил Корпан, за времето на евакуацията кораба успява да транспортира над 4 хиляди души, сред които болшинството са пострадали от огнестрелни рани, а много от бежанците са в критическо състояние.
По време на провеждането на евакуационната мисия „Константин Олшанский“ и още един кораб, БДК-69, (от проекта 1171) са подложени на нападение от няколко въоръжени катери от ВМС на Абхазия. Командира на „Олшански“ взема решението да следва страничен курс и да подготови оръдията си за стрелба, обаче съседният кораб, МДК-123, от проекта 1232.2 „Зубр“ се притичва на помощ и с огън от установката си АК-630М потопява един от катерите, съумявайки да отхвърли силите на противника.
22 марта 2011 г. корабль прибыл в Либия, където се разгаря гражданска война, за евакуирането на гражданите на Украйна. На борда са приети 193 души, от тях 85 граждани на Украйна и 108 граждани на 14 други страни. На 4 април кораба пристига в Малта, където са свалени 79 души. На 11 април кораба пристига в Севастопол, доставяйки там гражданите на Украйна и страните от ОНД[2][3][4].
На 24 марта 2014 г. „Константин Олшанский“ е превзет от руски военнослужещи, на кораба е вдигнат Андреевския флаг[5]. Според съобщението на украинските СМИ, от екипажа е извадена от строя двигателната установка и електронното оборудване[6].
През ноември 2015 г. на кораба започват ремонтно-възстановителни и бояджийски работи[8]. На кораба е разположен екипаж със съкратен състав, необходим за подсигуряването на живота на кораба[9]
Към 2019 г. се намира под контрола на Руската Федерация.
Командири на кораба
капитан 2 ранг Савченко, Георгий Николаевич – 1996 – 1998 г.;
капитан 2 ранг Гречухин, Олег Валентинович – 1998 – 1999 г.;
капитан 1 ранг Елисеев, Сергей Станиславович – 1999 – 2001 г.;
капитан капитан 2 ранг Деренский, Дмитрий Георгиевич – 2001 – 2005 г.;
капитан 2 ранг Гладкий, Роман Миколайович – 2005 – 2009 г.;
